/proc/sys/kernel/pid_max issues
Hi,
I tried creating 100,000 threads just for the hell of it. I was surprised that it appears to have worked even with pid_max set at 32k.
It seems if we are above pid_max we wrap back to RESERVED_PIDS at the start of alloc_pidmap but do not enforce this upper limit. I guess every call of alloc_pidmap above 32k was wrapping back to RESERVED_PIDS, walking the allocated space then allocating off the end.
Just as an aside, does it make sense to remove the pidmap allocator and use the IDR allocator now its there?
Now once I had managed to allocate those 100,000 threads, I noticed this:
18446744071725383682 dr-xr-xr-x 3 root root 0 Sep 12 08:10 100796
Strange huh. Turns out we allocate inodes in proc via:
#define fake_ino(pid,ino) (((pid)<<16)|(ino))
With 32bit inodes we are screwed once pids go over 64k arent we?
Anton
Quoted 6 lines · Anton Blanchard
I tried creating 100,000 threads just for the hell of it. I was surprised that it appears to have worked even with
pid_maxset at 32k. It seems if we are abovepid_maxwe wrap back toRESERVED_PIDSat the start ofalloc_pidmapbut do not enforce this upper limit. I guess every call ofalloc_pidmapabove 32k was wrapping back toRESERVED_PIDS, walking the allocated space then allocating off the end.
Well, it looks like things blindly move to the next bitmap block and don't check that the offset within it is valid, so the patch below (not runtime or compile-time tested) may help. It relies on next_free_map() returning NULL after having cycled through enough of the bitmap blocks.
Quoted 8 lines · Anton Blanchard
Just as an aside, does it make sense to remove the pidmap allocator and use the IDR allocator now its there?
Now once I had managed to allocate those 100,000 threads, I noticed this:
18446744071725383682 dr-xr-xr-x 3 root root 0 Sep 12 08:10 100796
Strange huh. Turns out we allocate inodes in proc via:
#definefake_ino(pid,ino)(((pid)<<16)|(ino))
With 32bit inodes we are screwed once pids go over 64k arent we?
The /proc/ code is rather messy around this area so I don't have any immediate ideas there.
-- wli
kernel/pid.c +4 -3
@@ -75,6 +75,8 @@while (--*max_steps) {if (++map == map_limit) map = pidmap_array; +if (map > &pidmap_array[pid_max/BITS_PER_PAGE ]) + map = pidmap_array;if (unlikely (!map->page)) {unsigned long page =get_zeroed_page (GFP_KERNEL );/*
@@ -135,13 +137,12 @@*/ scan_more: offset =find_next_zero_bit (map->page,BITS_PER_PAGE , offset); -if (offset >=BITS_PER_PAGE ) + pid = (map - pidmap_array) *BITS_PER_PAGE + offset; +if (offset >=BITS_PER_PAGE || pid >= pid_max) goto next_map;if (test_and_set_bit (offset, map->page)) goto scan_more; -/* we got the PID: */ - pid = (map - pidmap_array) *BITS_PER_PAGE + offset; goto return_pid; failure:
kernel/pid.c line 146
Quoted 13 lines · William Lee Irwin III
kernel/pid.c +4
-3+if (map > &pidmap_array[pid_max/BITS_PER_PAGE ]) + map = pidmap_array; -if (offset >=BITS_PER_PAGE ) + pid = (map - pidmap_array) *BITS_PER_PAGE + offset; +if (offset >=BITS_PER_PAGE || pid >= pid_max) goto next_map;if (test_and_set_bit (offset, map->page)) goto scan_more; -/* we got the PID: */ - pid = (map - pidmap_array) *BITS_PER_PAGE + offset; goto return_pid;
i missed the wrapping, so your patch is the right one:
Ingo
Review
Quoted 4 lines · William Lee Irwin III
(quoted diff) +2
-0+ if (map > &pidmap_array[pid_max/BITS_PER_PAGE]) + map = pidmap_array; if (unlikely(!map->page)) { unsigned long page = get_zeroed_page(GFP_KERNEL);
If pid_max == BITS_PER_PAGE*n, none of &pidmap_array[pid_max/BITS_PER_PAGE] is usable, so if we must complete a full revolution around pidmap_array[] to discover a free pid slightly less than last_pid we will miss it. Hence:
-- wli
kernel/pid.c +4 -3
@@ -75,6 +75,8 @@while (--*max_steps) {if (++map == map_limit) map = pidmap_array; +if (map > &pidmap_array[(pid_max-1 )/BITS_PER_PAGE ]) + map = pidmap_array;if (unlikely (!map->page)) {unsigned long page =get_zeroed_page (GFP_KERNEL );/*
@@ -135,13 +137,12 @@*/ scan_more: offset =find_next_zero_bit (map->page,BITS_PER_PAGE , offset); -if (offset >=BITS_PER_PAGE ) + pid = (map - pidmap_array) *BITS_PER_PAGE + offset; +if (offset >=BITS_PER_PAGE || pid >= pid_max) goto next_map;if (test_and_set_bit (offset, map->page)) goto scan_more; -/* we got the PID: */ - pid = (map - pidmap_array) *BITS_PER_PAGE + offset; goto return_pid; failure:
Quoted 4 lines · William Lee Irwin III
Quoted 4 lines
kernel/pid.c +2
-0+if (map > &pidmap_array[pid_max/BITS_PER_PAGE ]) + map = pidmap_array;if (unlikely (!map->page)) {unsigned long page =get_zeroed_page (GFP_KERNEL );
Quoted 3 lines · William Lee Irwin III
If
pid_max== BITS_PER_PAGE*n, none of &pidmap_array[pid_max/BITS_PER_PAGE] is usable, so if we must complete a full revolution around pidmap_array[] to discover a free pid slightly less thanlast_pidwe will miss it. Hence:
That could only happen if max_steps were initialized to PIDMAP_ENTRIES instead of PIDMAP_ENTRIES + 1, so this more accurate upper bound is not strictly necessary, though with this in place, we could probably reduce max_steps to just PIDMAP_ENTRIES so we cycle no further than the block we began; I'll not bother with that.
-- wli
Quoted 4 lines · William Lee Irwin III
If
pid_max== BITS_PER_PAGE*n, none of &pidmap_array[pid_max/BITS_PER_PAGE] is usable, so if we must complete a full revolution around pidmap_array[] to discover a free pid slightly less thanlast_pidwe will miss it. Hence:
yeah. Patch needs testing ...
Review
Quoted 4 lines
(quoted diff) +2
-0if (++map == map_limit) map = pidmap_array; + if (map > &pidmap_array[(pid_max-1)/BITS_PER_PAGE]) + map = pidmap_array;
in fact we can now merge the max_limit and pid_max checks - see the attached updated patch.
Ingo
fix pid_max handling. Wrap around correctly.
kernel/pid.c renamed from kernel/pid.c.orig +5 -6
@@ -53,8 +53,6 @@ typedef struct pidmap {static pidmap_t pidmap_array[PIDMAP_ENTRIES ] = { [0 ...PIDMAP_ENTRIES -1 ] = {ATOMIC_INIT (BITS_PER_PAGE ),NULL } }; -static pidmap_t *map_limit = pidmap_array +PIDMAP_ENTRIES ; - static spinlock_t pidmap_lock __cacheline_aligned_in_smp = SPIN_LOCK_UNLOCKED; fastcall void free_pidmap(int pid)
@@ -73,7 +71,9 @@ fastcall void free_pidmap(int pid)static inline pidmap_t *next_free_map (pidmap_t *map,int *max_steps) {while (--*max_steps) { -if (++map == map_limit) +pidmap_t *map_limit = pidmap_array + (pid_max-1 )/BITS_PER_PAGE ; + +if (++map > map_limit) map = pidmap_array;if (unlikely (!map->page)) {unsigned long page =get_zeroed_page (GFP_KERNEL );
@@ -133,13 +133,12 @@ next_map:*/ scan_more: offset =find_next_zero_bit (map->page,BITS_PER_PAGE , offset); -if (offset >=BITS_PER_PAGE ) + pid = (map - pidmap_array) *BITS_PER_PAGE + offset; +if (offset >=BITS_PER_PAGE || pid >= pid_max) goto next_map;if (test_and_set_bit (offset, map->page)) goto scan_more; -/* we got the PID: */ - pid = (map - pidmap_array) *BITS_PER_PAGE + offset; goto return_pid; failure:
Quoted 5 lines · Ingo Molnar
in fact we can now merge the
max_limitandpid_maxchecks - see the attached updated patch.
fixpid_maxhandling. Wrap around correctly.Signed-off-by William Lee Irwin III <[email protected]>Signed-off-by Ingo Molnar <[email protected]>
I like the update. But I see other issues. For instance (also untested):
pid wrapping doesn't honor RESERVED_PIDS.
kernel/pid.c +4 -1
@@ -128,7 +128,10 @@ map =next_free_map (map, &max_steps);if (!map) goto failure; - offset =0 ; +else if (map != pidmap_array) + offset =0 ; +else + offset =RESERVED_PIDS ; }/* * Find the next zero bit:
Quoted 2 lines · William Lee Irwin III
I like the update. But I see other issues. For instance (also untested):
pid wrapping doesn't honorRESERVED_PIDS.
Also:
last_pid is not honored because next_free_map(map - 1, ...) may return the same map and so restart with a lesser offset.
kernel/pid.c +6 -4
@@ -120,10 +120,12 @@ last_pid = pid;return pid; } - -if (!offset || !atomic_read (&map->nr_free)) { -if (!offset) - map--; +if (!offset) { +if (!atomic_read (&map->nr_free)) + goto next_map; +else + goto scan_more; + }else if (!atomic_read (&map->nr_free)) { next_map: map =next_free_map (map, &max_steps);if (!map)
Quoted 2 lines · William Lee Irwin III
Quoted 2 lines
I like the update. But I see other issues. For instance (also untested):
pid wrapping doesn't honorRESERVED_PIDS.
Quoted 2 lines · William Lee Irwin III
last_pidis not honored becausenext_free_map(map - 1, ...)may return the same map and so restart with a lesser offset.
Forgot to check map->page in the first spin:
last_pid is not honored because next_free_map(map - 1, ...) may return the same map and so restart with a lesser offset.
kernel/pid.c +30 -17
@@ -64,6 +64,21 @@atomic_inc (&map->nr_free); } +static void alloc_pidmap_page (pidmap_t *map) +{ +unsigned long page =get_zeroed_page (GFP_KERNEL ); +/* +* Free the page if someone raced with us +* installing it: +*/ +spin_lock (&pidmap_lock); +if (map->page) +free_page (page); +else + map->page = (void *)page; +spin_unlock (&pidmap_lock); +} +/* * Here we search for the next map that has free bits left. * Normally the next map has free PIDs.
@@ -76,18 +91,7 @@if (++map > map_limit) map = pidmap_array;if (unlikely (!map->page)) { -unsigned long page =get_zeroed_page (GFP_KERNEL ); -/* -* Free the page if someone raced with us -* installing it: -*/ -spin_lock (&pidmap_lock); -if (map->page) -free_page (page); -else - map->page = (void *)page; -spin_unlock (&pidmap_lock); - +alloc_pidmap_page (map);if (!map->page)break ; }
@@ -119,11 +123,20 @@atomic_dec (&map->nr_free); last_pid = pid;return pid; - } - -if (!offset || !atomic_read (&map->nr_free)) { -if (!offset) - map--; + }else if (!offset) { +if (map->page) { +if (atomic_read (&map->nr_free)) + goto scan_more; +else + goto next_map; + }else { +alloc_pidmap_page (map); +if (map->page) + goto scan_more; +else + goto failure; + } + }else if (!atomic_read (&map->nr_free)) { next_map: map =next_free_map (map, &max_steps);if (!map)
Quoted 4 lines · William Lee Irwin III
Forgot to check
map->pagein the first spin:
last_pidis not honored becausenext_free_map(map - 1, ...)may return the same map and so restart with a lesser offset.
it's getting quite spaghetti ... do we really want to handle RESERVED_PID? There's no guarantee that any root daemon wont stray out of the 1...300 PID range anyway, so if it has an exploitable PID race bug then it's probably exploitable even without the RESERVED_PID protection.
Ingo
Quoted 3 lines · William Lee Irwin III
Quoted 3 lines
Forgot to check
map->pagein the first spin:last_pidis not honored becausenext_free_map(map - 1, ...)may return the same map and so restart with a lesser offset.
Quoted 5 lines · Ingo Molnar
it's getting quite spaghetti ... do we really want to handle
RESERVED_PID? There's no guarantee that any root daemon wont stray out of the 1...300 PID range anyway, so if it has an exploitable PID race bug then it's probably exploitable even without theRESERVED_PIDprotection.
I presumed it was merely cosmetic, so daemons around system startup will get low pid numbers recognizable by sysadmins. Maybe filtering process listings for pids < 300 is/was used to find daemons that may have crashed? I'm not particularly attached to the feature, and have never used it myself, but merely noticed its implementation was off.
Spaghetti may mean it's time to rewrite things. The following is a goto-less alloc_pidmap() vs. 2.6.9-rc1-mm4 addressing all stated concerns, but otherwise changing none of the semantics. Untested.
-- wli
kernel/pid.c +32 -65
@@ -38,6 +38,9 @@#define PIDMAP_ENTRIES (PID_MAX_LIMIT/PAGE_SIZE/8)#define BITS_PER_PAGE (PAGE_SIZE*8)#define BITS_PER_PAGE_MASK (BITS_PER_PAGE-1) +#define mk_pid (map, off) (((map) - pidmap_array)*BITS_PER_PAGE + (off)) +#define find_next_offset (map, off) \ + find_next_zero_bit((map)->page, BITS_PER_PAGE, off)/* * PID-map pages start out as NULL, they get allocated upon
@@ -53,8 +56,6 @@static pidmap_t pidmap_array[PIDMAP_ENTRIES ] = { [0 ...PIDMAP_ENTRIES -1 ] = {ATOMIC_INIT (BITS_PER_PAGE ),NULL } }; -static pidmap_t *map_limit = pidmap_array +PIDMAP_ENTRIES ; - static spinlock_t pidmap_lock __cacheline_aligned_in_smp = SPIN_LOCK_UNLOCKED; fastcall void free_pidmap(int pid)
@@ -66,15 +67,16 @@atomic_inc (&map->nr_free); } -/* -* Here we search for the next map that has free bits left. -* Normally the next map has free PIDs. -*/ -static inline pidmap_t *next_free_map (pidmap_t *map,int *max_steps) +int alloc_pidmap (void ) { -while (--*max_steps) { -if (++map == map_limit) - map = pidmap_array; +int i, offset, pid = last_pid +1 ; +pidmap_t *map; + +if (pid >= pid_max) + pid =RESERVED_PIDS ; + offset = pid &BITS_PER_PAGE_MASK ; + map = &pidmap_array[pid/BITS_PER_PAGE ]; +for (i =0 ; i <PIDMAP_ENTRIES ; ++i) {if (unlikely (!map->page)) {unsigned long page =get_zeroed_page (GFP_KERNEL );/*
@@ -87,64 +89,29 @@else map->page = (void *)page;spin_unlock (&pidmap_lock); - -if (!map->page) +if (unlikely (!map->page))break ; } -if (atomic_read (&map->nr_free)) -return map; - } -return NULL ; -} - -int alloc_pidmap (void ) -{ -int pid, offset, max_steps =PIDMAP_ENTRIES +1 ; -pidmap_t *map; - - pid = last_pid +1 ; -if (pid >= pid_max) - pid =RESERVED_PIDS ; - - offset = pid &BITS_PER_PAGE_MASK ; - map = pidmap_array + pid /BITS_PER_PAGE ; - -if (likely (map->page && !test_and_set_bit (offset, map->page))) { -/* -* There is a small window for last_pid updates to race, -* but in that case the next allocation will go into the -* slowpath and that fixes things up. -*/ -return_pid: -atomic_dec (&map->nr_free); - last_pid = pid; -return pid; - } - -if (!offset || !atomic_read (&map->nr_free)) { -if (!offset) - map--; -next_map: - map =next_free_map (map, &max_steps); -if (!map) - goto failure; - offset =0 ; +if (likely (atomic_read (&map->nr_free))) { +do { +if (!test_and_set_bit (offset, map->page)) { +atomic_dec (&map->nr_free); + last_pid = pid; +return pid; + } + offset =find_next_offset (map, offset); + pid =mk_pid (map, offset); + }while (offset <BITS_PER_PAGE && pid < pid_max); + } +if (map < &pidmap_array[(pid_max-1 )/BITS_PER_PAGE ]) { + ++map; + offset =0 ; + }else { + map = &pidmap_array[0 ]; + offset =RESERVED_PIDS ; + } + pid =mk_pid (map, offset); } -/* -* Find the next zero bit: -*/ -scan_more: - offset =find_next_zero_bit (map->page,BITS_PER_PAGE , offset); -if (offset >=BITS_PER_PAGE ) - goto next_map; -if (test_and_set_bit (offset, map->page)) - goto scan_more; - -/* we got the PID: */ - pid = (map - pidmap_array) *BITS_PER_PAGE + offset; - goto return_pid; - -failure:return -1 ; }
Quoted 5 lines · William Lee Irwin III
I presumed it was merely cosmetic, so daemons around system startup will get low pid numbers recognizable by sysadmins. Maybe filtering process listings for pids < 300 is/was used to find daemons that may have crashed? I'm not particularly attached to the feature, and have never used it myself, but merely noticed its implementation was off.
I always assumed it was an optimization when looking for a new PID after a wrap by trying to skip over the kernel threads. Arguably 300 is way too small for larger systems (which might have several thousand kernel threads) and should probably be sized on boot (or when starting userspace) if anyone really cares.
Quoted 5 lines · William Lee Irwin III
Quoted 5 lines
I presumed it was merely cosmetic, so daemons around system startup will get low pid numbers recognizable by sysadmins. Maybe filtering process listings for pids < 300 is/was used to find daemons that may have crashed? I'm not particularly attached to the feature, and have never used it myself, but merely noticed its implementation was off.
Quoted 5 lines · Chris Wedgwood
I always assumed it was an optimization when looking for a new PID after a wrap by trying to skip over the kernel threads. Arguably 300 is way too small for larger systems (which might have several thousand kernel threads) and should probably be sized on boot (or when starting userspace) if anyone really cares.
There's no reason it couldn't be made tunable, though we may want to place restrictions on what values are allowed, e.g. reserved_pids > 0 and reserved_pids < min(BITS_PER_PAGE, pid_max). For that matter, we should likely be using proc_dointvec_minmax() for pid_max or otherwise a custom strategy function if we need to update bounds on reserved_pids and/or reserved_pids in tandem. I suspect this is obscure enough I should leave it alone unless someone develops a strong opinion about it.
-- wli
[pidhashing] rewrite alloc_pidmap()
In reply to William Lee Irwin IIIQuoted 3 lines · William Lee Irwin III
Spaghetti may mean it's time to rewrite things. The following is a goto-less
alloc_pidmap()vs. 2.6.9-rc1-mm4 addressing all stated concerns, but otherwise changing none of the semantics. Untested.
The original version was broken wrt. wrapping.
It needs to allow enough iterations to return to the same block as we started to allow fallback to go as far as just behind last_pid in the same bitmap block that covers last_pid when last_pid + 1 is BITS_PER_PAGE-unaligned. Also remove redundant scanning by bounding the loop according to pid_max, the saved last_pid, and the alignment of offset, as such prevents rapid-fire pid reuse by avoiding scanning any part of the bitmap more than once or out of cyclic order starting from last_pid + 1, never reusing the last_pid seen in a given call in that call. The corner cases aren't that easily reproducible, but it's best to find glaring errors early, so I've compiled and booted this now that I'm back at home, and checked that it boots okay, generates reasonable pid lists, and doesn't fall over or allocate pids below RESERVED_PIDS during pid wraps on x86-64.
vs. 2.6.9-rc1-mm4. Patch description follows signature.
-- wli
Rewrite alloc_pidmap() to clarify control flow by eliminating all usage of goto, honor pid_max and first available pid after last_pid semantics, make only a single pass over the used portion of the pid bitmap, and update copyrights to reflect ongoing maintenance by Ingo and myself.
kernel/pid.c +46 -67
@@ -1,8 +1,8 @@/* * Generic pidhash and scalable, time-bounded PID allocator * -* (C) 2002 William Irwin, IBM -* (C) 2002 Ingo Molnar, Red Hat +* (C) 2002-2004 William Irwin, Oracle +* (C) 2002-2004 Ingo Molnar, Red Hat * * pid-structures are backing objects for tasks sharing a given ID to chain * against. There is very little to them aside from hashing them and
@@ -38,6 +38,9 @@#define PIDMAP_ENTRIES (PID_MAX_LIMIT/PAGE_SIZE/8)#define BITS_PER_PAGE (PAGE_SIZE*8)#define BITS_PER_PAGE_MASK (BITS_PER_PAGE-1) +#define mk_pid (map, off) (((map) - pidmap_array)*BITS_PER_PAGE + (off)) +#define find_next_offset (map, off) \ + find_next_zero_bit((map)->page, BITS_PER_PAGE, off)/* * PID-map pages start out as NULL, they get allocated upon
@@ -53,8 +56,6 @@static pidmap_t pidmap_array[PIDMAP_ENTRIES ] = { [0 ...PIDMAP_ENTRIES -1 ] = {ATOMIC_INIT (BITS_PER_PAGE ),NULL } }; -static pidmap_t *map_limit = pidmap_array +PIDMAP_ENTRIES ; - static spinlock_t pidmap_lock __cacheline_aligned_in_smp = SPIN_LOCK_UNLOCKED; fastcall void free_pidmap(int pid)
@@ -66,15 +67,18 @@atomic_inc (&map->nr_free); } -/* -* Here we search for the next map that has free bits left. -* Normally the next map has free PIDs. -*/ -static inline pidmap_t *next_free_map (pidmap_t *map,int *max_steps) +int alloc_pidmap (void ) { -while (--*max_steps) { -if (++map == map_limit) - map = pidmap_array; +int i, offset, max_scan, pid, last = last_pid; +pidmap_t *map; + + pid = last +1 ; +if (pid >= pid_max) + pid =RESERVED_PIDS ; + offset = pid &BITS_PER_PAGE_MASK ; + map = &pidmap_array[pid/BITS_PER_PAGE ]; + max_scan = (pid_max +BITS_PER_PAGE -1 )/BITS_PER_PAGE - !offset; +for (i =0 ; i <= max_scan; ++i) {if (unlikely (!map->page)) {unsigned long page =get_zeroed_page (GFP_KERNEL );/*
@@ -87,64 +91,39 @@else map->page = (void *)page;spin_unlock (&pidmap_lock); - -if (!map->page) +if (unlikely (!map->page))break ; } -if (atomic_read (&map->nr_free)) -return map; - } -return NULL ; -} - -int alloc_pidmap (void ) -{ -int pid, offset, max_steps =PIDMAP_ENTRIES +1 ; -pidmap_t *map; - - pid = last_pid +1 ; -if (pid >= pid_max) - pid =RESERVED_PIDS ; - - offset = pid &BITS_PER_PAGE_MASK ; - map = pidmap_array + pid /BITS_PER_PAGE ; - -if (likely (map->page && !test_and_set_bit (offset, map->page))) { -/* -* There is a small window for last_pid updates to race, -* but in that case the next allocation will go into the -* slowpath and that fixes things up. -*/ -return_pid: -atomic_dec (&map->nr_free); - last_pid = pid; -return pid; - } - -if (!offset || !atomic_read (&map->nr_free)) { -if (!offset) - map--; -next_map: - map =next_free_map (map, &max_steps); -if (!map) - goto failure; - offset =0 ; +if (likely (atomic_read (&map->nr_free))) { +do { +if (!test_and_set_bit (offset, map->page)) { +atomic_dec (&map->nr_free); + last_pid = pid; +return pid; + } + offset =find_next_offset (map, offset); + pid =mk_pid (map, offset); +/* +* find_next_offset() found a bit, the pid from it +* is in-bounds, and if we fell back to the last +* bitmap block and the final block was the same +* as the starting point, pid is before last_pid. +*/ + }while (offset <BITS_PER_PAGE && pid < pid_max && + (i != max_scan || pid < last || + !((last+1 ) &BITS_PER_PAGE_MASK ))); + } +if (map < &pidmap_array[(pid_max-1 )/BITS_PER_PAGE ]) { + ++map; + offset =0 ; + }else { + map = &pidmap_array[0 ]; + offset =RESERVED_PIDS ; +if (unlikely (last == offset)) +break ; + } + pid =mk_pid (map, offset); } -/* -* Find the next zero bit: -*/ -scan_more: - offset =find_next_zero_bit (map->page,BITS_PER_PAGE , offset); -if (offset >=BITS_PER_PAGE ) - goto next_map; -if (test_and_set_bit (offset, map->page)) - goto scan_more; - -/* we got the PID: */ - pid = (map - pidmap_array) *BITS_PER_PAGE + offset; - goto return_pid; - -failure:return -1 ; }
Quoted 8 lines · Anton Blanchard
I tried creating 100,000 threads just for the hell of it. I was surprised that it appears to have worked even with
pid_maxset at 32k.It seems if we are above
pid_maxwe wrap back toRESERVED_PIDSat the start ofalloc_pidmapbut do not enforce this upper limit. I guess every call ofalloc_pidmapabove 32k was wrapping back toRESERVED_PIDS, walking the allocated space then allocating off the end.
yeah. Does the attached patch fix it?
Quoted 2 lines
Just as an aside, does it make sense to remove the pidmap allocator and use the IDR allocator now its there?
might make sense - needs benchmarking. In particular the performance of kill(pid, 0) [PID lookup] should be benchmarked on the cycle level, and the combined performance of pthread_create()+pthread_exit().
Quoted 10 lines
Now once I had managed to allocate those 100,000 threads, I noticed this:
18446744071725383682 dr-xr-xr-x 3 root root 0 Sep 12 08:10 100796
Strange huh. Turns out we allocate inodes in proc via:
#define
fake_ino(pid,ino)(((pid)<<16)|(ino))With 32bit inodes we are screwed once pids go over 64k arent we?
indeed.
i'm wondering, dont we have a similar problem with PROC_TID_FD_DIR already? Running some simple code that opens 1 million files gives:
[root@saturn root]# ulimit -n 1000000
[root@saturn root]# ./open-fds 1000000
999997 fds opened
[root@saturn root]# cd /proc/2333/fd/
[root@saturn fd]# ls -li | grep 153028253
153028253 lrwx------ 1 root root 64 Sep 12 11:18 165533 -> /dev/pts/0 153028253 lrwx------ 1 root root 64 Sep 12 11:18 362141 -> /dev/pts/0 153028253 lrwx------ 1 root root 64 Sep 12 11:18 427677 -> /dev/pts/0 153028253 lrwx------ 1 root root 64 Sep 12 11:18 624285 -> /dev/pts/0 153028253 lrwx------ 1 root root 64 Sep 12 11:19 689821 -> /dev/pts/0 153028253 lrwx------ 1 root root 64 Sep 12 11:18 99997 -> /dev/pts/0
[...]
plenty of overlap in the #ino space.
Ingo
kernel/pid.c renamed from kernel/pid.c.orig +5 -1
@@ -103,7 +103,7 @@ int alloc_pidmap(void)pidmap_t *map; pid = last_pid +1 ; -if (pid >= pid_max) +if (unlikely (pid >= pid_max)) pid =RESERVED_PIDS ; offset = pid &BITS_PER_PAGE_MASK ;
@@ -116,6 +116,10 @@ int alloc_pidmap(void)* slowpath and that fixes things up. */ return_pid: +if (unlikely (pid >= pid_max)) { +clear_bit (offset, map->page); + goto failure; + }atomic_dec (&map->nr_free); last_pid = pid;return pid;
kernel/pid.c int alloc_pidmap(void) · line 107
Quoted 9 lines · Ingo Molnar
kernel/pid.c renamed from kernel/pid.c.orig +1
-1@@ -103,7 +103,7 @@ int alloc_pidmap(void)pidmap_t *map; pid = last_pid +1 ; -if (pid >= pid_max) +if (unlikely (pid >= pid_max)) pid =RESERVED_PIDS ;
Well, this part won't change the wrapping behavior.
kernel/pid.c int alloc_pidmap(void) · line 125
Quoted 12 lines · Ingo Molnar
kernel/pid.c renamed from kernel/pid.c.orig +4
-0offset = pid &BITS_PER_PAGE_MASK ;@@ -116,6 +116,10 @@ int alloc_pidmap(void)* slowpath and that fixes things up. */ return_pid: +if (unlikely (pid >= pid_max)) { +clear_bit (offset, map->page); + goto failure; + }atomic_dec (&map->nr_free); last_pid = pid;return pid;
This is too late; it hands back a hard failure without resetting last_pid.
-- wli
Quoted 4 lines · Anton Blanchard
Hi,
I tried creating 100,000 threads just for the hell of it. I was surprised that it appears to have worked even with
pid_maxset at 32k.
there are a lot of other reasons why you can't go over 64k threads ;) (esp on a 32 bit machine)
such as all the 16 bit counters in rwsems etc etc... Just Say No(tm) :)
Quoted 3 lines
there are a lot of other reasons why you can't go over 64k threads ;) (esp on a 32 bit machine)
After all the effort of going to 4kB stacks on x86? :)
Quoted 2 lines
such as all the 16 bit counters in rwsems etc etc... Just Say No(tm) :)
Hmm can you point the 16bit counter out? I can create 1 million NPTL threads on ppc64 easily, so why not?
As Ingo points out the same proc inode overflow happens with applications with lots of FDs.
Anton
Quoted 3 lines · Anton Blanchard
Hmm can you point the 16bit counter out? I can create 1 million NPTL threads on ppc64 easily, so why not?
/*
* the semaphore definition
*/
struct rw_semaphore {
/* XXX this should be able to be an atomic_t -- paulus */
signed int count;
#define RWSEM_UNLOCKED_VALUE 0x00000000
#define RWSEM_ACTIVE_BIAS 0x00000001
#define RWSEM_ACTIVE_MASK 0x0000ffffthat counter is split in 2 16 bit entities....
Quoted 4 lines
/*
* the semaphore definition
*/
Quoted 8 lines
struct rw_semaphore { /* XXX this should be able to be an atomic_t -- paulus */ signed int count; #define RWSEM_UNLOCKED_VALUE 0x00000000 #define RWSEM_ACTIVE_BIAS 0x00000001 #define RWSEM_ACTIVE_MASK 0x0000ffffthat counter is split in 2 16 bit entities....
Yuck, 64k waiters is asking for trouble. BTW x86-64 mentions it can only handle 32k writers, that probably wants looking at.
Anton
Quoted 8 lines · Arjan van de Ven
Quoted 3 lines · Anton Blanchard
Hmm can you point the 16bit counter out? I can create 1 million NPTL threads on ppc64 easily, so why not?
/*
* the semaphore definition
*/
Quoted 8 lines
struct rw_semaphore { /* XXX this should be able to be an atomic_t -- paulus */ signed int count; #define RWSEM_UNLOCKED_VALUE 0x00000000 #define RWSEM_ACTIVE_BIAS 0x00000001 #define RWSEM_ACTIVE_MASK 0x0000ffffthat counter is split in 2 16 bit entities....
the generic semaphore code can handle up to ~2^31 waiters. I once tried it on x86, it seems to work fine.
Ingo