Kernel Traffic #172 For 23 Jun 2002

STOP!

What madness is this?

You have a damn mutex system call, don't introduce mode crap in /dev.

Do we create pipes by opening /dev/pipe? No. Do we have major and minor numbers for sockets and populate /dev with them? No. And as a result, there has _never_ been any sysadmin problems with either.

You already have to have a system call to bind the particular fd to the futex _anyway_, so do the only sane thing, and allocate the fd _there_, and get rid of that stupid and horrible /dev/futex which only buys you pain, system administration, extra code, and a black star for being stupid.

Tell me _one_ advantage from having the thing exposed as a filename?

The whole point with "everything is a file" is not that you have some random filename (indeed, sockets and pipes show that "file" and "filename" have nothing to do with each other), but the fact that you can use common tools to operate on different things.

But there's absolutely no point in opening /dev/futex from a shell script or similar, because you don't get anything from it. You still have to bind the fd to it's real object.

In short, the name "/dev/futex/index.html" (or "/proc/futex/index.html") is _meaningless_. There's no point to it. It has no life outside the FUTEX system call, and the only thing that you can do by exposing it as a name is to cause problems for people who don't want to mount /proc, or who do not happen to have that device node in their /dev.

I don't think it's a matter of cutting, as much as possibly a matter of tryign to share some common code. pipefs, sockfs and now this: they all do pretty much exactly the same thing, and there is nothing that says that they should have separate super_operations, for example, since they are all identical.

And once you have the same super_operations, you really have the same "fill_super" functions too. The only thing that separates these superblocks is the root name, so that /proc gets nice output. So it should be fine to just have

>sb = create_anon_fs("futex");

and share all of the setup code across futex/pipes/sockfs.

Which still leaves you with the

get_unused_fd();
get_empty_filp();
filp->f_dentry = dget(sb->s_root);
.. fill it ..
fd_install(fd, filp);

but by then we're talking single lines of overhead.

the point is not that it would be a performance hit on "exit()", but that WE DON'T TRACK THE LOCKS in the kernel in the first place.

Right now the kernel does _zero_ work for a lock that isn't contended. It doesn't know _anything_ about the process that got the lock initially.

Any amount of tracking would be _extremely_ expensive. Right now getting an uncontended lock is about 15 CPU cycles in user space.

Tryin to tell the kernel about gettign that lock takes about 1us on a P4 (system call overhead), ie we're talking 18000 cycles. 18 THOUSAND cycles minimum. Compared to the current 15 cycles. That's more than three orders of magnitude slower than the current code, and you just lost the whole point of doing this all in user space in the first place.

Oh, agreed, you can do debugging locks in user-space, but it won't be the kernel that does anything, it will instead have to depend on something like "if I time out on the lock, I can explicitly test if the previous holder (who saved his thread ID in memory after getting the lock) is still alive and try to clean up after him".

This is what a lot of the filesystem locking code does for the things in /var/lock/xxx, of course.

No kernel necessarily involved.

But it's going to have to depend on the politeness of all threads that partake in the locking.

For a while I've been wanting a way for a program to find out if any of its socket buffers were overflowing due to too much incoming traffic. Finally, I decided to code it up and try it out.

As it turns out, it was relatively simple to add, although it required the addition of two new entries in sockios.h.

Basically, inside of sock_queue_rcv_skb() and sock_queue_err_skb() the receive counter gets incremented unconditionally, and then if there is no free space in the socket buffer then we also increment the counter for messages dropped due to out of memory.

The stats are stored as part of a socket_stats struct, making it easy to add other counters in the future.

To access and reset the counters, two ioctl commands were added to the socket ioctl. GIOCSOCKSTATS is used to get the stats, while SIOCZEROSOCKSTATS is used to reset them. I haven't bothered with trying to reset them both atomically as I don't think it's that critical.

The patch was coded and tested for 2.4.18, but it is known to at least apply (with offsets) on 2.5.20.

The linux coding style _tends_ to avoid using typedefs. It's not a hard rule (and I did in fact apply this patch, since it otherwise looked fine), but it's fairly common to use an explicit "struct xxxx" instead of "xxxx_t".

I dislike type abstraction if it has no real reason. And saving on typing is not a good reason - if your typing speed is the main issue when you're coding, you're doing something seriously wrong.

(Similarly, if you are trying to compress lines to be shorter, you have other problems, nothing to do with type names).

Does code look "prettier" with a "_t" rather than a "struct "? I don't know. I personally don't think so, and I also hate the "_p" (or even more the just plain "p") convention for "pointer".

Hiding the fact that it's a struct causes bad things if people don't realize it: allocating structs on the stack is something you should be aware of (and careful with), and passing them as parameters is is much better done explicitly as a "pointer to struct".

There are _some_ exceptions. For example, "pte_t" etc might well be a struct on most architectures, and that's ok: it's expressly designed to be an opaque (and still fairly small) thing. This is an example of where there are clear _reasons_ for the abstraction, not just abstraction for its own sake.

But in the end, maintainership matters. I personally don't want the typedef culture to get the upper hand, but I don't mind a few of them, and people who maintain their own code usually get the last word.

Well, it's more than just "struct xx". It's really typedefs in general.

For example, some people like to do things like

typedef unsigned int counter_t;

and then use "counter_t" all over the place. I think that's not just ugly, but stupid and counter-productive. It makes it much harder to do things like "printk()" portably, for example ("should I use %u, %l or just %d?"), and generally adds no value. It only _hides_ information, like whether the type is signed or not.

There is nothing wrong with just using something like "unsigned long" directly, even if it is a few characters longer than you might like. And if you care about the number of bits, use "u32" or something. Don't make up useless types that have no added advantage.

We actually have real _problems_ due to this in the kernel, where people use "off_t", and it's not easily printk'able across different architectures (we used to have this same problem with size_t). We should have just used "unsigned long" inside the kernel, and be done with it (and "unsigned long long" for loff_t).

We should also have some format for printing out "u32/u64" etc, but that's another issue and has the problem that gcc won't understand them, so adding new formats is _hard_ from a maintenance standpoint.

PS. And never _ever_ make the "pointerness" part of the type. People who write

typedef struct urb_struct * urbp_t;

(or whatever the name was) should just be shot. I was _soo_ happy to see that crap get excised from the kernel USB drivers.

There is no such thing as a non-recursive symlink resolution.

Symlink walking is by it's very nature recursive, since we have to be able to look a symlink up in the middle of another one.

So either it's recursive in C (caller ends up calling itself) or it linearizes the recursion by hand (caller keeps track of the stack by hand using a linked list or by expanding the pathname in place or whatever, instead of using the C stack).

Both are recursive, it's only a question of whether the recursion is handled by the language or by hand, and whether the interim state is held on the stack or in explicit data structures.

I see no advantages to handling it by hand, since this isn't even a very deep recursion, and since even if you do the recursive part by hand by a linked list you still need to limit the depth _anyway_ to avoid DoS attacks.

In fact, we avoid following symlinks too deeply even for the _non_recursive_ case (see "total_link_count") exactly because of these DoS issues.

Could we allow deeper recursion if we did it by hand? Sure. Are there any real advantages in 15 levels of recursion over 5 levels of recursion? I don't see any.

It's the recursive trip through the filesystem that causes the problem. Suddenly the stack space consumption becomes (N * greediest_filesystem) and that has to be factored into all worst case calculations. It's a huge hole to blow out of this severely restricted resource, so reducing N to 1 is a big deal.

Also, as a practical matter, it's much easier to lay down a rule for filesystem developers that reads: "thou shalt in no case use more than N bytes of stack on your longest path" than "in no case use more than N bytes of stack except on any symlink resolution path, in which case see the limit on recursive symlinks to know how to analyze that path".

Actually, the trip to the filesystem itself is not recursive. We only have one lookup _active_ at a time, so the stack depth is fairly well bounded. I think at some point it was on the order of 64 bytes per invocation on x86. It really isn't as bad as people have made it out to be.

(But yes, the x86 is denser on the stack than many architectures)

Note that I'm absolutely not adverse to have people test Andries patch, and I don't _mind_ it. I'm really arguing not so much against the patch itself, as against the _religious_ and unthinking reaction against a perfectly fine programming construct (limited recursion).

PS. Yes, a filesystem can do stupid things, and make the actual single level function have a huge stack-frame: the example was for the normal "page_symlink" thing.

In your previous letter you wanted to play semantical tricks with the word recursive, even though you understood perfectly well what I meant with "nonrecursive" (and you yourself used the same terminology in older posts).

Now I hesitate whether I should react to the above statement. Maybe this time there are semantical tricks with the word active, but it sounds a bit as if you misunderstand the situation.

Let me state the facts instead of worrying about semantics.

The routine link_path_walk() in namei.c will call do_follow_link() in case of a symlink, and this routine will call dentry->d_inode->i_op->follow_link(), say, nfs_follow_link(), which calls vfs_follow_link(), which calls link_path_walk(), etc.

You see that in a stack of N invocations, there will also be N stack frames of foofs_follow_link(). So, yes, in the way I use recursive, routines like nfs_follow_link() are indeed recursive: they end up calling themselves.

Last Sunday or so I gave a demo patch that takes the filesystems out of the loop. Then symlink resolution is still recursive but there will be at most one invocation of foofs_follow_link().

Yesterday I showed that it is also easy to avoid recursion altogether.

These are independent stages, and one might consider doing one and not the other.

Yes. But did you look at the stack frames of those things? It's something like 16 bytes for ext2_follow_link (it just calls directly back to the VFS layer), 20 bytes for vfs_follow_link(), and 56 for link_path_walk.

(yeah, it obviously isn't just 64 bytes any more, it's 92 bytes. Maybe I just counted wrong last time. Or maybe link_path_walk is different enough).

Oh, and I think the actual ->follow_link pushes 8 bytes of arguments.

So doing a recursion 5 deep is ~500 bytes of stack space.

That was my point: the _only_ difference between "explicit recursion" and "recurse by hand" is where and how those intermediate bytes are allocated. There is nothing inherently "evil" in letting the compiler do it for you.

And as you found out yourself, a recursion limit of 5 is actually a lot more than people normally use.

But hey, guys, if you want to linearize the recursion, I'm easily swayed by numbers. I've actually done the numbers for stack usage (exactly because I worried about it some time ago), and I don't worry too much about that number. I also don't worry about the number "5", simply because I don't think I've _ever_ gotten a complaint about it that I remember.

But there are other numbers, like performance (sometimes linearizing recursion loses, sometimes it wins), or somebody doing the math on ia-64 and showing that the 100 bytes/level on x86 is actually more like 2kB on ia-64 and totally unacceptable.

But trying to sell this thing to me as a "recursion is evil and must be stamped out" just doesn't work.

I realize you probably missed the history. There was a discussion about large stack variables found by Checker, and how Checker might have difficulties getting the max stack right in the presence of this recursion.

I remarked that it is trivial to remove the recursion, should anyone be interested in that, but Al called such claims false and wrong, so I did half of the work (removing the filesystems from the loop) three days ago, and Al said that it was nothing yet, actually removing the recursion would be hell. So I removed the recursion yesterday evening. A demo project.

(And you were cc'ed only because I happened to come across what I think is a refcounting buglet in the present code.)

Have not heard from Al yet, but my secret hope is that he'll soon come back and tell me that my code is ugly and contains seventeen bugs but that he has done it right with elegant, fast and maintainable code.

In the meantime, no, this was not a patch submission, it was for discussion and because Al wanted to see actual code.