Skip to contentSkip to conversation

fdtable: Eradicate fdarray overflow.

PATCH In review Vadim Lobanov 2 participants 5 messages Oct 12, 2006 VFS

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 fdtable: Eradicate fdarray overflow.

Andrew,

If you want it, here is the "actual patch format" fix for the random kernel bug issue that has been discovered. This patch is functionally identical to the one you grabbed, but contains comments and sign-offs.

Fix the computation of the length of an allocated fdarray, when we decide to grow the fdtable. The rationale behind this fix is as follows:
=> The 'nr' variable is the requested fd, so will be one less than the minimum
allowable fdarray size.
=> Due to the above fact, when we divide 'nr' by a fourth-of-a-page block, we
will always be exactly one block short of the size we need.
=> Incrementing before the division is wrong, because the division will discard
a non-zero modulo, possibly leaving us one fourth-of-a-page block short.

fs/file.c +1 -2
diff -Npru old/fs/file.c new/fs/file.c
@@ -164,9 +164,8 @@ static struct fdtable * alloc_fdtable(un
 	 * the fdarray into page-sized chunks: starting at a quarter of a page,
 	 * and growing in powers of two from there on.
 	 */
-	nr++;
 	nr /= (PAGE_SIZE / 4 / sizeof(struct file *));
-	nr = roundup_pow_of_two(nr);
+	nr = roundup_pow_of_two(nr + 1);
 	nr *= (PAGE_SIZE / 4 / sizeof(struct file *));
 	if (nr > NR_OPEN)
 		nr = NR_OPEN;
#1 lore raw
Quoted 5 lines · Vadim Lobanov

diff -Npru old/fs/file.c new/fs/file.c

fs/file.c static struct fdtable * alloc_fdtable(un · line 171

Quoted 10 lines
fs/file.c +1 -2
@@ -164,9 +164,8 @@ static struct fdtable * alloc_fdtable(un
 	 * the fdarray into page-sized chunks: starting at a quarter of a page,
 	 * and growing in powers of two from there on.
 	 */
-	nr++;
 	nr /= (PAGE_SIZE / 4 / sizeof(struct file *));
-	nr = roundup_pow_of_two(nr);
+	nr = roundup_pow_of_two(nr + 1);
 	nr *= (PAGE_SIZE / 4 / sizeof(struct file *));
 	if (nr > NR_OPEN)
 		nr = NR_OPEN;

Hi Vadim

I find your PAGE_SIZE/4 minimum allocation quite unjustified.

For architectures with 64K PAGE_SIZE, we endup allocating 16K, for poor tasks that happen to touch a not so high (>= 64) file descriptor...

I would vote for a fixed size, like 1024

Eric

#2 lore raw
Quoted 8 lines · Eric Dumazet

Hi Vadim

I find your PAGE_SIZE/4 minimum allocation quite unjustified.

For architectures with 64K PAGE_SIZE, we endup allocating 16K, for poor tasks that happen to touch a not so high (>= 64) file descriptor...

I would vote for a fixed size, like 1024

In my opinion, always picking 1024 would be highly suboptimal for some architectures (x86-64 in particular -- that's a whole page, just for the fdarray!). If anything, I'd prefer something similar to this pseudo-code:

#define FDTABLE_MIN min_t(uint, PAGE_SIZE / 4 / sizeof(struct file *), 1024)
...
nr /= FDTABLE_MIN;
nr = roundup_pow_of_two(nr + 1);
nr *= FDTABLE_MIN;

gcc should be smart enough to optimize that expression into a single constant. At least it did (version 4.1.0) in my quick test here.

Quoted 1 line

Eric

Let me know what you think. Please don't just go radio-silent on me. ;)

-- Vadim Lobanov

#3 lore raw
Quoted 11 lines · Vadim Lobanov
Quoted 8 lines · Eric Dumazet

Hi Vadim

I find your PAGE_SIZE/4 minimum allocation quite unjustified.

For architectures with 64K PAGE_SIZE, we endup allocating 16K, for poor tasks that happen to touch a not so high (>= 64) file descriptor...

I would vote for a fixed size, like 1024

In my opinion, always picking 1024 would be highly suboptimal for some architectures (x86-64 in particular -- that's a whole page, just for the fdarray!). If anything, I'd prefer something similar to this pseudo-code:

I was speaking of 1024 bytes.

I was the guy who made fdset going from PAGE_SIZE to 64 bytes (L1_CACHE_BYTES if you dare), I wont be the guy responsible for a reverse path on fdtable :)

That is replace your (PAGE_SIZE/4) by 1024, wich was you probably meant No archi has a smaller page, so no need to play with min_t() macro...

Quoted 7 lines

#define FDTABLE_MIN min_t(uint, PAGE_SIZE / 4 / sizeof(struct file *), 1024)
...
nr /= FDTABLE_MIN;
nr = roundup_pow_of_two(nr + 1);
nr *= FDTABLE_MIN;

Quoted 6 lines

gcc should be smart enough to optimize that expression into a single constant. At least it did (version 4.1.0) in my quick test here.

Quoted 1 line

Eric

Let me know what you think. Please don't just go radio-silent on me. ;)

radio-silent ? well, it seems I already sent you many mails about your patches :)

Eric

#4 lore raw
Quoted 9 lines · Eric Dumazet
Quoted 8 lines · Vadim Lobanov
Quoted 7 lines · Eric Dumazet

Hi Vadim

I find your PAGE_SIZE/4 minimum allocation quite unjustified.

For architectures with 64K PAGE_SIZE, we endup allocating 16K, for poor tasks that happen to touch a not so high (>= 64) file descriptor...

Quoted 7 lines
Quoted 5 lines
Quoted 1 line

I would vote for a fixed size, like 1024

In my opinion, always picking 1024 would be highly suboptimal for some architectures (x86-64 in particular -- that's a whole page, just for the fdarray!). If anything, I'd prefer something similar to this pseudo-code:

I was speaking of 1024 bytes.

Oh, well, that does make a difference! :) I misread your email: I thought you were suggesting 1024 fdarray entries, not 1024 bytes. I'd agree with you completely then.

Quoted 2 lines

That is replace your (PAGE_SIZE/4) by 1024, wich was you probably meant No archi has a smaller page, so no need to play with min_t() macro...

Good point. Code can then simply become:
nr /= (1024 / sizeof(struct file *));
nr = roundup_pow_of_two(nr + 1);
nr *= (1024 / sizeof(struct file *));

Quoted 4 lines
Quoted 1 line

Let me know what you think. Please don't just go radio-silent on me. ;)

radio-silent ? well, it seems I already sent you many mails about your patches :)

Your feedback is very much appreciated, believe me! :) Both you (for the ideas) and akpm (for his assistance and seemingly-infinite patience, even when I accidentally broke his tree (I owe him a few beers/other-goodies for that)) have helped out tremendously with this.

So far, I have two comments from you that I need to take care of:
1) allocate at least L1_CACHE_BYTES for fdsets
2) change PAGE_SIZE/4 to 1024
Both are performance tweaks, not crash fixes, and are easy to do. Could you please look through the rest of the code in fs/file.c and point out any other issues or code tweaks you can see? My plan is to prepare patches for these things and buffer them up, and when we're done tweaking, I'll forward the whole batch on to akpm.

Then, once everything has settled down for a long while, I'll send out the final fs/file.c cleanups patch -- mostly it introduces extensive comments into that file about why the code does what it does.

Quoted 1 line

Eric

-- Vadim Lobanov