Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.unix.programmer > #306 > unrolled thread
| Started by | boltar2003@boltar.world |
|---|---|
| First post | 2011-05-05 09:37 +0000 |
| Last post | 2011-05-05 12:18 -0700 |
| Articles | 20 on this page of 270 — 46 participants |
Back to article view | Back to comp.unix.programmer
Avoiding recursive stack overflow in C on Unix/Linux? boltar2003@boltar.world - 2011-05-05 09:37 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? China Blue Veins <chine.bleu@yahoo.com> - 2011-05-05 02:51 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? boltar2003@boltar.world - 2011-05-05 09:58 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? China Blue Veins <chine.bleu@yahoo.com> - 2011-05-05 04:47 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? scott@slp53.sl.home (Scott Lurndal) - 2011-05-07 23:22 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? Xavier Roche <xroche@free.fr.NOSPAM.invalid> - 2011-05-05 11:58 +0200
Re: Avoiding recursive stack overflow in C on Unix/Linux? Geoff Clare <geoff@clare.See-My-Signature.invalid> - 2011-05-05 13:40 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? boltar2003@boltar.world - 2011-05-05 13:52 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? Azazel <azazel@remove.azazel.net> - 2011-05-05 09:22 -0500
Re: Avoiding recursive stack overflow in C on Unix/Linux? boltar2003@boltar.world - 2011-05-05 14:41 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? Azazel <azazel@remove.azazel.net> - 2011-05-05 10:30 -0500
Re: Avoiding recursive stack overflow in C on Unix/Linux? scott@slp53.sl.home (Scott Lurndal) - 2011-05-07 23:23 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? Xavier Roche <xroche@free.fr.NOSPAM.invalid> - 2011-05-05 18:55 +0200
Re: Avoiding recursive stack overflow in C on Unix/Linux? William Ahern <william@wilbur.25thandClement.com> - 2011-05-05 11:58 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Xavier Roche <xroche@free.fr.NOSPAM.invalid> - 2011-05-06 14:36 +0200
RLIMIT_STACK (was: Avoiding recursive stack overflow in C on Unix/Linux?) Geoff Clare <geoff@clare.See-My-Signature.invalid> - 2011-05-10 14:19 +0100
Re: RLIMIT_STACK Xavier Roche <xroche@free.fr.NOSPAM.invalid> - 2011-05-11 08:28 +0200
Re: RLIMIT_STACK scott@slp53.sl.home (Scott Lurndal) - 2011-05-11 16:18 +0000
Re: RLIMIT_STACK Xavier Roche <xroche@free.fr.NOSPAM.invalid> - 2011-05-11 18:37 +0200
Re: RLIMIT_STACK scott@slp53.sl.home (Scott Lurndal) - 2011-05-11 19:53 +0000
Re: RLIMIT_STACK Geoff Clare <geoff@clare.See-My-Signature.invalid> - 2011-05-11 17:43 +0100
Re: RLIMIT_STACK Xavier Roche <xroche@free.fr.NOSPAM.invalid> - 2011-05-11 20:03 +0200
Re: RLIMIT_STACK Xavier Roche <xroche@free.fr.NOSPAM.invalid> - 2011-05-11 20:20 +0200
Re: Avoiding recursive stack overflow in C on Unix/Linux? Nobody <nobody@nowhere.com> - 2011-05-06 03:27 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? "robertwessel2@yahoo.com" <robertwessel2@yahoo.com> - 2011-05-06 00:03 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? boltar2003@boltar.world - 2011-05-06 09:18 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? "robertwessel2@yahoo.com" <robertwessel2@yahoo.com> - 2011-05-06 02:56 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Noob <root@127.0.0.1> - 2011-06-01 15:19 +0200
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-05 12:24 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Lowell Gilbert <lgusenet@be-well.ilk.org> - 2011-05-05 15:40 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-06 02:18 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-05-05 21:17 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Datesfat Chicks <datesfat.chicks@gmail.com> - 2011-05-05 18:45 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-06 02:44 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? boltar2003@boltar.world - 2011-05-06 09:58 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? Richard Kettlewell <rjk@greenend.org.uk> - 2011-05-06 11:11 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? boltar2003@boltar.world - 2011-05-06 10:16 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? Richard Kettlewell <rjk@greenend.org.uk> - 2011-05-06 11:28 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-06 02:34 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Michael Press <rubrum@pacbell.net> - 2011-05-06 15:09 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Dr Nick <3-nospam@temporary-address.org.uk> - 2011-05-07 13:03 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Barry Margolin <barmar@alum.mit.edu> - 2011-05-07 09:01 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? Dr Nick <3-nospam@temporary-address.org.uk> - 2011-05-07 14:32 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Rainer Weikusat <rweikusat@mssgmbh.com> - 2011-05-07 16:27 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Dr Nick <3-nospam@temporary-address.org.uk> - 2011-05-07 16:43 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Jorgen Grahn <grahn+nntp@snipabacken.se> - 2011-05-08 06:19 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? Rainer Weikusat <rweikusat@mssgmbh.com> - 2011-05-08 17:18 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-05-08 09:58 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? boltar2003@boltar.world - 2011-05-09 11:34 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? Nick Keighley <nick_keighley_nospam@hotmail.com> - 2011-05-11 03:48 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? boltar2003@boltar.world - 2011-05-11 10:51 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? Keith Thompson <kst-u@mib.org> - 2011-05-11 08:11 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? boltar2003@boltar.world - 2011-05-11 15:47 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? Nick Keighley <nick_keighley_nospam@hotmail.com> - 2011-05-12 15:05 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? boltar2003@boltar.world - 2011-05-07 16:23 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? Barry Margolin <barmar@alum.mit.edu> - 2011-05-07 18:12 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-07 10:30 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Nobody <nobody@nowhere.com> - 2011-05-07 20:01 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-07 12:37 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Barry Margolin <barmar@alum.mit.edu> - 2011-05-07 18:15 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? Michael Press <rubrum@pacbell.net> - 2011-05-08 15:26 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? William Ahern <william@wilbur.25thandClement.com> - 2011-05-07 09:32 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Ian Collins <ian-news@hotmail.com> - 2011-05-08 10:46 +1200
Re: Avoiding recursive stack overflow in C on Unix/Linux? William Ahern <william@wilbur.25thandClement.com> - 2011-05-07 21:49 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-07 09:59 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Dr Nick <3-nospam@temporary-address.org.uk> - 2011-05-07 20:24 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Michael Press <rubrum@pacbell.net> - 2011-05-07 15:04 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-07 15:15 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Michael Press <rubrum@pacbell.net> - 2011-05-07 21:02 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Nobody <nobody@nowhere.com> - 2011-05-07 19:57 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Dr Nick <3-nospam@temporary-address.org.uk> - 2011-05-07 20:26 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Nobody <nobody@nowhere.com> - 2011-05-07 21:06 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? scott@slp53.sl.home (Scott Lurndal) - 2011-05-07 23:27 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? James Kuyper <jameskuyper@verizon.net> - 2011-05-05 20:07 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-05-06 02:53 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? "io_x" <a@b.c.invalid> - 2011-05-08 19:27 +0200
Re: Avoiding recursive stack overflow in C on Unix/Linux? Måns Rullgård <mans@mansr.com> - 2011-05-06 10:07 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Måns Rullgård <mans@mansr.com> - 2011-05-06 10:29 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-05-06 03:04 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? James Kuyper <jameskuyper@verizon.net> - 2011-05-06 06:33 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? Måns Rullgård <mans@mansr.com> - 2011-05-06 12:04 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? David Schwartz <davids@webmaster.com> - 2011-05-07 04:11 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Måns Rullgård <mans@mansr.com> - 2011-05-07 13:07 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? David Schwartz <davids@webmaster.com> - 2011-05-07 21:13 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Måns Rullgård <mans@mansr.com> - 2011-05-08 10:46 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? David Schwartz <davids@webmaster.com> - 2011-05-08 05:11 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Golden California Girls <gldncagrls@aol.com.mil> - 2011-05-07 08:59 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-06 02:58 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? James Kuyper <jameskuyper@verizon.net> - 2011-05-06 07:08 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-06 08:18 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Marco Parrone <marco@marcoparrone.com> - 2011-05-06 17:32 +0200
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-06 08:51 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? James Kuyper <jameskuyper@verizon.net> - 2011-05-06 21:46 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-07 00:28 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? James Kuyper <jameskuyper@verizon.net> - 2011-05-07 09:01 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-07 06:35 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? James Kuyper <jameskuyper@verizon.net> - 2011-05-07 22:52 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-08 01:26 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Dr Nick <3-nospam@temporary-address.org.uk> - 2011-05-08 09:37 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-05-08 03:21 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Willem <willem@toad.stack.nl> - 2011-05-08 10:44 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-08 07:23 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? boltar2003@boltar.world - 2011-05-09 11:30 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? Rainer Weikusat <rweikusat@mssgmbh.com> - 2011-05-09 13:36 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-05-09 07:08 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Ian Collins <ian-news@hotmail.com> - 2011-05-10 07:38 +1200
Re: Avoiding recursive stack overflow in C on Unix/Linux? Ian Collins <ian-news@hotmail.com> - 2011-05-10 07:44 +1200
Re: Avoiding recursive stack overflow in C on Unix/Linux? Rainer Weikusat <rweikusat@mssgmbh.com> - 2011-05-09 21:44 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-09 13:59 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-09 14:19 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Michael Press <rubrum@pacbell.net> - 2011-05-09 15:05 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Ian Collins <ian-news@hotmail.com> - 2011-05-10 10:20 +1200
Re: Avoiding recursive stack overflow in C on Unix/Linux? Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2011-05-14 19:04 +0300
Re: Avoiding recursive stack overflow in C on Unix/Linux? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-05-14 11:13 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Joshua Maurice <joshuamaurice@gmail.com> - 2011-05-09 15:40 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Måns Rullgård <mans@mansr.com> - 2011-05-09 23:44 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Ian Collins <ian-news@hotmail.com> - 2011-05-10 11:06 +1200
Re: Avoiding recursive stack overflow in C on Unix/Linux? Måns Rullgård <mans@mansr.com> - 2011-05-10 00:11 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Ian Collins <ian-news@hotmail.com> - 2011-05-10 11:17 +1200
Re: Avoiding recursive stack overflow in C on Unix/Linux? Dr Nick <3-nospam@temporary-address.org.uk> - 2011-05-10 07:10 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Michael Press <rubrum@pacbell.net> - 2011-05-10 12:24 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? ImpalerCore <jadill33@gmail.com> - 2011-05-10 13:43 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? pete <pfiland@mindspring.com> - 2011-05-11 08:48 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? pete <pfiland@mindspring.com> - 2011-05-11 08:54 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? ImpalerCore <jadill33@gmail.com> - 2011-05-12 05:56 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Dr Nick <3-nospam@temporary-address.org.uk> - 2011-05-11 00:44 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Michael Press <rubrum@pacbell.net> - 2011-05-10 19:36 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? pete <pfiland@mindspring.com> - 2011-05-10 23:21 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? Dr Nick <3-nospam@temporary-address.org.uk> - 2011-05-11 07:08 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Casper H.S. Dik <Casper.Dik@OrSPaMcle.COM> - 2011-05-11 11:48 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? James Kuyper <jameskuyper@verizon.net> - 2011-05-11 10:03 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? James Kuyper <jameskuyper@verizon.net> - 2011-05-11 10:12 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? Dr Nick <3-nospam@temporary-address.org.uk> - 2011-05-11 21:23 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Nicolas George <nicolas$george@salle-s.org> - 2011-05-11 21:07 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-05-12 09:45 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? pete <pfiland@mindspring.com> - 2011-05-11 08:00 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? Michael Press <rubrum@pacbell.net> - 2011-05-11 19:35 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Dr Nick <3-nospam@temporary-address.org.uk> - 2011-05-12 06:51 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Michael Press <rubrum@pacbell.net> - 2011-05-12 14:36 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Dr Nick <3-nospam@temporary-address.org.uk> - 2011-05-12 22:57 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Casper H.S. Dik <Casper.Dik@OrSPaMcle.COM> - 2011-05-11 11:47 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? pete <pfiland@mindspring.com> - 2011-05-11 08:07 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? Keith Thompson <kst-u@mib.org> - 2011-05-10 21:16 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? "robertwessel2@yahoo.com" <robertwessel2@yahoo.com> - 2011-05-11 02:40 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? pete <pfiland@mindspring.com> - 2011-05-11 09:39 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? Michael Press <rubrum@pacbell.net> - 2011-05-11 19:42 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2011-05-15 00:23 +0300
Re: Avoiding recursive stack overflow in C on Unix/Linux? pacman@kosh.dhis.org (Alan Curry) - 2011-05-14 22:30 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Ersek, Laszlo" <lacos@caesar.elte.hu> - 2011-05-15 18:21 +0200
Re: Avoiding recursive stack overflow in C on Unix/Linux? Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2011-05-16 04:19 +0300
Re: Avoiding recursive stack overflow in C on Unix/Linux? Keith Thompson <kst-u@mib.org> - 2011-05-16 08:40 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-05-16 17:53 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Nicolas George <nicolas$george@salle-s.org> - 2011-05-16 16:58 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? Barry Margolin <barmar@alum.mit.edu> - 2011-05-16 21:39 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? Keith Thompson <kst-u@mib.org> - 2011-05-17 09:12 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? "robertwessel2@yahoo.com" <robertwessel2@yahoo.com> - 2011-05-17 10:20 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? pete <pfiland@mindspring.com> - 2011-05-17 15:00 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? pacman@kosh.dhis.org (Alan Curry) - 2011-05-17 20:28 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? Keith Thompson <kst-u@mib.org> - 2011-05-17 14:45 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Keith Thompson <kst-u@mib.org> - 2011-05-17 14:51 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? "robertwessel2@yahoo.com" <robertwessel2@yahoo.com> - 2011-05-17 16:23 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-05-17 23:06 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? "robertwessel2@yahoo.com" <robertwessel2@yahoo.com> - 2011-05-18 01:02 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-05-18 01:29 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? "robertwessel2@yahoo.com" <robertwessel2@yahoo.com> - 2011-05-18 04:03 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Ben Pfaff <blp@cs.stanford.edu> - 2011-05-17 16:47 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Keith Thompson <kst-u@mib.org> - 2011-05-17 17:21 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2011-05-23 21:57 +0300
Re: Avoiding recursive stack overflow in C on Unix/Linux? Jonathan de Boyne Pollard <J.deBoynePollard-newsgroups@NTLWorld.COM> - 2011-05-23 21:57 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? "robertwessel2@yahoo.com" <robertwessel2@yahoo.com> - 2011-05-23 17:45 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Rainer Weikusat <rweikusat@mssgmbh.com> - 2011-05-24 11:43 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? "robertwessel2@yahoo.com" <robertwessel2@yahoo.com> - 2011-05-24 10:58 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Sherm Pendley <sherm.pendley@gmail.com> - 2011-05-11 11:11 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? Michael Press <rubrum@pacbell.net> - 2011-05-11 19:48 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Keith Thompson <kst-u@mib.org> - 2011-05-09 16:22 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Michael Press <rubrum@pacbell.net> - 2011-05-09 21:25 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Seebs <usenet-nospam@seebs.net> - 2011-05-10 17:28 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? Michael Press <rubrum@pacbell.net> - 2011-05-09 17:11 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Ian Collins <ian-news@hotmail.com> - 2011-05-10 12:20 +1200
Re: Avoiding recursive stack overflow in C on Unix/Linux? pete <pfiland@mindspring.com> - 2011-05-10 03:53 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? Ian Collins <ian-news@hotmail.com> - 2011-05-10 20:18 +1200
Re: Avoiding recursive stack overflow in C on Unix/Linux? pete <pfiland@mindspring.com> - 2011-05-10 04:42 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? boltar2003@boltar.world - 2011-05-10 09:12 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-05-10 03:21 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? boltar2003@boltar.world - 2011-05-10 10:53 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-10 08:12 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? pete <pfiland@mindspring.com> - 2011-05-10 09:39 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? Michael Press <rubrum@pacbell.net> - 2011-05-10 12:51 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Ian Collins <ian-news@hotmail.com> - 2011-05-11 08:12 +1200
Re: Avoiding recursive stack overflow in C on Unix/Linux? Joshua Maurice <joshuamaurice@gmail.com> - 2011-05-10 15:16 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Michael Press <rubrum@pacbell.net> - 2011-05-10 19:43 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? James Kuyper <jameskuyper@verizon.net> - 2011-05-11 07:41 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? Michael Press <rubrum@pacbell.net> - 2011-05-11 19:51 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Rainer Weikusat <rweikusat@mssgmbh.com> - 2011-05-11 12:45 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-10 07:50 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Rainer Weikusat <rweikusat@mssgmbh.com> - 2011-05-10 11:04 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? James Kuyper <jameskuyper@verizon.net> - 2011-05-08 09:27 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-08 08:04 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? James Kuyper <jameskuyper@verizon.net> - 2011-05-08 22:50 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-09 00:18 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Nobody <nobody@nowhere.com> - 2011-05-08 19:49 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Måns Rullgård <mans@mansr.com> - 2011-05-08 20:05 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Keith Thompson <kst-u@mib.org> - 2011-05-08 13:44 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-09 00:22 -0700
Re: Avoiding recursive stack overflow in C? Jonathan de Boyne Pollard <J.deBoynePollard-newsgroups@NTLWorld.COM> - 2011-05-15 17:05 +0100
Re: Avoiding recursive stack overflow in C? James Kuyper <jameskuyper@verizon.net> - 2011-05-15 14:07 -0400
Re: Avoiding recursive stack overflow in C? Jonathan de Boyne Pollard <J.deBoynePollard-newsgroups@NTLWorld.COM> - 2011-05-15 22:49 +0100
Re: Avoiding recursive stack overflow in C? James Kuyper <jameskuyper@verizon.net> - 2011-05-15 21:08 -0400
Re: Avoiding recursive stack overflow in C? Rainer Weikusat <rweikusat@mssgmbh.com> - 2011-05-16 11:10 +0100
Re: Avoiding recursive stack overflow in C? Ilya Zakharevich <nospam-abuse@ilyaz.org> - 2011-05-16 08:04 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? Niklas Holsti <niklas.holsti@tidorum.invalid> - 2011-05-07 19:11 +0300
Re: Avoiding recursive stack overflow in C on Unix/Linux? "io_x" <a@b.c.invalid> - 2011-05-08 07:17 +0200
Re: Avoiding recursive stack overflow in C on Unix/Linux? Niklas Holsti <niklas.holsti@tidorum.invalid> - 2011-05-08 10:16 +0300
Re: Avoiding recursive stack overflow in C on Unix/Linux? "io_x" <a@b.c.invalid> - 2011-05-09 09:03 +0200
Re: Avoiding recursive stack overflow in C on Unix/Linux? boltar2003@boltar.world - 2011-05-06 08:59 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-06 03:01 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? James Kuyper <jameskuyper@verizon.net> - 2011-05-06 07:13 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-06 09:02 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Michael Press <rubrum@pacbell.net> - 2011-05-06 15:41 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-07 02:53 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? boltar2003@boltar.world - 2011-05-07 16:17 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? William Ahern <william@wilbur.25thandClement.com> - 2011-05-07 10:08 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Nobody <nobody@nowhere.com> - 2011-05-07 20:20 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? William Ahern <william@wilbur.25thandClement.com> - 2011-05-07 14:26 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Michael Press <rubrum@pacbell.net> - 2011-05-07 14:31 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? William Ahern <william@wilbur.25thandClement.com> - 2011-05-07 22:49 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Michael Press <rubrum@pacbell.net> - 2011-05-07 23:27 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Casper H.S. Dik <Casper.Dik@OrSPaMcle.COM> - 2011-05-07 17:22 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-07 10:24 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Casper H.S. Dik <Casper.Dik@OrSPaMcle.COM> - 2011-05-07 17:32 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-07 11:43 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Casper H.S. Dik <Casper.Dik@OrSPaMcle.COM> - 2011-05-08 10:57 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-08 08:09 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Nobody <nobody@nowhere.com> - 2011-05-08 19:41 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Xavier Roche <xroche@free.fr.NOSPAM.invalid> - 2011-05-08 17:59 +0200
Re: Avoiding recursive stack overflow in C on Unix/Linux? Xavier Roche <xroche@free.fr.NOSPAM.invalid> - 2011-05-09 09:01 +0200
Re: Avoiding recursive stack overflow in C on Unix/Linux? Nobody <nobody@nowhere.com> - 2011-05-07 20:41 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Keith Thompson <kst-u@mib.org> - 2011-05-07 12:48 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Casper H.S. Dik <Casper.Dik@OrSPaMcle.COM> - 2011-05-08 11:01 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? gazelle@shell.xmission.com (Kenny McCormack) - 2011-05-08 13:10 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? Nobody <nobody@nowhere.com> - 2011-05-08 19:51 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? scott@slp53.sl.home (Scott Lurndal) - 2011-05-08 22:21 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? gazelle@shell.xmission.com (Kenny McCormack) - 2011-06-04 12:54 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? Michael Press <rubrum@pacbell.net> - 2011-06-04 12:59 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? ImpalerCore <jadill33@gmail.com> - 2011-06-07 06:30 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Michael Press <rubrum@pacbell.net> - 2011-06-10 21:56 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-07 13:53 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Keith Thompson <kst-u@mib.org> - 2011-05-07 15:16 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Måns Rullgård <mans@mansr.com> - 2011-05-07 23:42 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Keith Thompson <kst-u@mib.org> - 2011-05-07 19:37 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? "io_x" <a@b.c.invalid> - 2011-05-08 07:17 +0200
Re: Avoiding recursive stack overflow in C on Unix/Linux? "io_x" <a@b.c.invalid> - 2011-05-08 09:24 +0200
Re: Avoiding recursive stack overflow in C on Unix/Linux? Måns Rullgård <mans@mansr.com> - 2011-05-08 10:36 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2011-05-14 13:29 +0300
Re: Avoiding recursive stack overflow in C on Unix/Linux? Nobody <nobody@nowhere.com> - 2011-05-08 08:37 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Casper H.S. Dik <Casper.Dik@OrSPaMcle.COM> - 2011-05-08 11:13 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? Joshua Maurice <joshuamaurice@gmail.com> - 2011-05-09 15:46 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Barry Margolin <barmar@alum.mit.edu> - 2011-05-08 00:28 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? William Ahern <william@wilbur.25thandClement.com> - 2011-05-07 23:06 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Dr Nick <3-nospam@temporary-address.org.uk> - 2011-05-08 07:30 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? scott@slp53.sl.home (Scott Lurndal) - 2011-05-08 15:51 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2011-05-14 13:33 +0300
Re: Avoiding recursive stack overflow in C on Unix/Linux? Barry Margolin <barmar@alum.mit.edu> - 2011-05-14 11:08 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? scott@slp53.sl.home (Scott Lurndal) - 2011-05-14 15:53 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? Jonathan de Boyne Pollard <J.deBoynePollard-newsgroups@NTLWorld.COM> - 2011-05-10 22:14 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Casper H.S. Dik <Casper.Dik@OrSPaMcle.COM> - 2011-05-08 11:08 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? Nobody <nobody@nowhere.com> - 2011-05-08 08:15 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? boltar2003@boltar.world - 2011-05-10 08:30 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? Nick Keighley <nick_keighley_nospam@hotmail.com> - 2011-05-11 03:43 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? William Ahern <william@wilbur.25thandClement.com> - 2011-05-05 12:18 -0700
Page 9 of 14 — ← Prev page 1 … 7 8 [9] 10 11 … 14 Next page →
| From | "robertwessel2@yahoo.com" <robertwessel2@yahoo.com> |
|---|---|
| Date | 2011-05-17 16:23 -0700 |
| Message-ID | <a8108bf0-8262-400b-91ef-35f4b95d005b@t19g2000yql.googlegroups.com> |
| In reply to | #599 |
On May 17, 4:51 pm, Keith Thompson <ks...@mib.org> wrote: > Keith Thompson <ks...@mib.org> writes: > > [...] > > > If I were designing a program that needs to sort arrays whose > > contents are not under my control, I'd avoid using an algorithm > > whose run-time behavior can vary tremendously depending on the > > nature of the input -- not just because of the possibility of > > malicious attacks, but because even random data could conceivably > > cause the same problem. Even if the problem is unlikely to occur, > > it's good to have one less thing to worry about. > > > If this were difficult to do, I'd stop and consider whether it's > > worth the effort, but it shouldn't be. Though a naive Quicksort > > algorithm does suffer from this problem, my guess is that most, > > perhaps all, library sorting algorithms avoid it, either by tweaking > > Quicksort or by using a different algorithm. > > On re-reading this, I realize that the sentence > > If this were difficult to do, I'd stop and consider whether it's > worth the effort, but it shouldn't be. > > was unclear. I meant that it shouldn't be difficult to do, not > that it shouldn't be worth the effort. > > > A concrete question: Are there any existing C library implementations > > of qsort() that are vulnerable to this kind of problem? > > I took a look at the glibc implementation of qsort(). It does > use Quicksort, but with some tweaks. It picks the pivot using a > median-of-three decision tree, it falls back to insertion sort for > small segments, it uses an explicit stack rather than recursion, > and it always handles the larger partition first. I don't know > whether this completely avoids the worst-case N**2 behavior or not, > but it should make it less likely to happen accidentally. It does *not*. Again, I recommend Musser's original Introsort paper for a quite interesting description of how to generate worst case sequences for the common variants of Quicksort. It's actually remarkably straight-forward.
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.mclean5@btinternet.com> |
|---|---|
| Date | 2011-05-17 23:06 -0700 |
| Message-ID | <ba2a5ac6-a1d7-4928-b148-de6dbb09c4d7@m10g2000yqd.googlegroups.com> |
| In reply to | #601 |
On May 18, 2:23 am, "robertwess...@yahoo.com" <robertwess...@yahoo.com> wrote: > > It does *not*. Again, I recommend Musser's original Introsort paper > for a quite interesting description of how to generate worst case > sequences for the common variants of Quicksort. It's actually > remarkably straight-forward. > You just shuffle the input. Then it becomes far more likely that the computer will break than that you hit a worst case or even a bad case.
[toc] | [prev] | [next] | [standalone]
| From | "robertwessel2@yahoo.com" <robertwessel2@yahoo.com> |
|---|---|
| Date | 2011-05-18 01:02 -0700 |
| Message-ID | <ae27074f-5070-4738-a2e8-74c5ace1dd21@c41g2000yqm.googlegroups.com> |
| In reply to | #606 |
On May 18, 1:06 am, Malcolm McLean <malcolm.mcle...@btinternet.com> wrote: > On May 18, 2:23 am, "robertwess...@yahoo.com"<robertwess...@yahoo.com> wrote: > > > It does *not*. Again, I recommend Musser's original Introsort paper > > for a quite interesting description of how to generate worst case > > sequences for the common variants of Quicksort. It's actually > > remarkably straight-forward. > > You just shuffle the input. Then it becomes far more likely that the > computer will break than that you hit a worst case or even a bad case. Where are we going to get the entropy to do a good shuffle? And if we just use a deterministic shuffle, it should be trivial for the attacker to reverse that before sending the data. Obviously intermediate approaches are possible (use 32 bit of entropy to select one of ~2**32 permutations, for example, possibly by using the entropy to seed a PRNG to drive the shuffle). And why would any of this be meaningfully easier, or faster, than just using an introsort or heapsort instead? Doing a shuffle+quicksort ought to be a bit faster than heapsort on small elements, assuming a reasonably fast shuffle. Heapsort will definitely be simpler to implement (heck, heapsort is simpler than quicksort with median-of- three and separate small partition handling anyway). Shuffle +quicksort will certainly be slower than introsort in the typical cases (where introsort is identical to a straight quicksort). Assuming the preexistence of a useable entropy source, shuffle +quicksort ought to be slightly simpler to implement than introsort.
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.mclean5@btinternet.com> |
|---|---|
| Date | 2011-05-18 01:29 -0700 |
| Message-ID | <5a611fd8-d57a-4dd3-8a91-87c21fb8a681@y4g2000yqm.googlegroups.com> |
| In reply to | #610 |
On May 18, 11:02 am, "robertwess...@yahoo.com" <robertwess...@yahoo.com> wrote: > > > Where are we going to get the entropy to do a good shuffle? > From the clock. The attacker can still time his input so that the clock comes up with the right number, but that's likely to be challenging. Certainly it will be a lot harder than getting the source for Microsoft Visual C++ qsort(), and engineering an input that takes N^3 iterations to complete.
[toc] | [prev] | [next] | [standalone]
| From | "robertwessel2@yahoo.com" <robertwessel2@yahoo.com> |
|---|---|
| Date | 2011-05-18 04:03 -0700 |
| Message-ID | <123d7165-a273-49c6-bb96-2c394a73ead7@z13g2000yqg.googlegroups.com> |
| In reply to | #611 |
On May 18, 3:29 am, Malcolm McLean <malcolm.mcle...@btinternet.com> wrote: > On May 18, 11:02 am, "robertwess...@yahoo.com"<robertwess...@yahoo.com> wrote: > > > Where are we going to get the entropy to do a good shuffle? > > From the clock. > The attacker can still time his input so that the clock comes up with > the right number, but that's likely to be challenging. Certainly it > will be a lot harder than getting the source for Microsoft Visual C++ > qsort(), and engineering an input that takes N^3 iterations to > complete. The clock is a poor source of entropy, especially if you're using actual time. Sure, timing is bit of a challenge, but nothing that hasn't been done before. FWIW, the source to MS's qsort is in vc\crt \src\qsort.c (assuming you installed source when you installed VS), and implements a slightly modified median-of-three quicksort. And quicksort's worst case is N**2.
[toc] | [prev] | [next] | [standalone]
| From | Ben Pfaff <blp@cs.stanford.edu> |
|---|---|
| Date | 2011-05-17 16:47 -0700 |
| Message-ID | <8762p851pm.fsf@blp.benpfaff.org> |
| In reply to | #599 |
Keith Thompson <kst-u@mib.org> writes: > I took a look at the glibc implementation of qsort(). It does > use Quicksort, but with some tweaks. It picks the pivot using a > median-of-three decision tree, it falls back to insertion sort for > small segments, it uses an explicit stack rather than recursion, > and it always handles the larger partition first. I don't know > whether this completely avoids the worst-case N**2 behavior or not, > but it should make it less likely to happen accidentally. It also uses merge sort instead of quicksort when enough memory is available. -- Ben Pfaff http://benpfaff.org
[toc] | [prev] | [next] | [standalone]
| From | Keith Thompson <kst-u@mib.org> |
|---|---|
| Date | 2011-05-17 17:21 -0700 |
| Message-ID | <lnzkmk505h.fsf@nuthaus.mib.org> |
| In reply to | #602 |
Ben Pfaff <blp@cs.stanford.edu> writes:
> Keith Thompson <kst-u@mib.org> writes:
>> I took a look at the glibc implementation of qsort(). It does
>> use Quicksort, but with some tweaks. It picks the pivot using a
>> median-of-three decision tree, it falls back to insertion sort for
>> small segments, it uses an explicit stack rather than recursion,
>> and it always handles the larger partition first. I don't know
>> whether this completely avoids the worst-case N**2 behavior or not,
>> but it should make it less likely to happen accidentally.
>
> It also uses merge sort instead of quicksort when enough memory
> is available.
What I wrote above appears to be only a subset of the truth.
I grabbed the glibc sources and took a quick look at qsort.c
(mostly just skimming the comments). Had I looked more closely,
I would have realized that qsort.c doesn't actually define qsort().
qsort() is defined in msort.c; it's a wrapper around qsort_r, which
*sometimes* calls the _quicksort function that's defined in qsort.c.
--
Keith Thompson (The_Other_Keith) kst-u@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
[toc] | [prev] | [next] | [standalone]
| From | Phil Carmody <thefatphil_demunged@yahoo.co.uk> |
|---|---|
| Date | 2011-05-23 21:57 +0300 |
| Message-ID | <87aaedtfcb.fsf@bazspaz.fatphil.org> |
| In reply to | #599 |
Keith Thompson <kst-u@mib.org> writes: > Keith Thompson <kst-u@mib.org> writes: > [...] > > If I were designing a program that needs to sort arrays whose > > contents are not under my control, I'd avoid using an algorithm > > whose run-time behavior can vary tremendously depending on the > > nature of the input -- not just because of the possibility of > > malicious attacks, but because even random data could conceivably > > cause the same problem. Even if the problem is unlikely to occur, > > it's good to have one less thing to worry about. > > > > If this were difficult to do, I'd stop and consider whether it's > > worth the effort, but it shouldn't be. Though a naive Quicksort > > algorithm does suffer from this problem, my guess is that most, > > perhaps all, library sorting algorithms avoid it, either by tweaking > > Quicksort or by using a different algorithm. > > On re-reading this, I realize that the sentence > > If this were difficult to do, I'd stop and consider whether it's > worth the effort, but it shouldn't be. > > was unclear. I meant that it shouldn't be difficult to do, not > that it shouldn't be worth the effort. > > > A concrete question: Are there any existing C library implementations > > of qsort() that are vulnerable to this kind of problem? > > I took a look at the glibc implementation of qsort(). It does > use Quicksort, but with some tweaks. It picks the pivot using a > median-of-three decision tree, it falls back to insertion sort for > small segments, it uses an explicit stack rather than recursion, > and it always handles the larger partition first. Odd, in order to reduce actual recursion (and do tail recursion instead), and to keep locality of reference tight, I'd handle the smaller part first were I to use an actual quicksort. Not that I'd do that, being more of a fan of heapsort in situations where I want an acceptable worst-case big-Oh for reasons such as availability. > I don't know > whether this completely avoids the worst-case N**2 behavior or not, > but it should make it less likely to happen accidentally. Nope, reduces the constant, that's all. If the median is selected from 3 random (i.e. unpredicatable to an attacker) elements, then the worst case behaviour can not be forced, and you would average to the theoretical average. But then you have to secure information about your (P)RNG state. Phil -- "At least you know where you are with Microsoft." "True. I just wish I'd brought a paddle." -- Matthew Vernon
[toc] | [prev] | [next] | [standalone]
| From | Jonathan de Boyne Pollard <J.deBoynePollard-newsgroups@NTLWorld.COM> |
|---|---|
| Date | 2011-05-23 21:57 +0100 |
| Message-ID | <IU.D20110523.T205837.P9147.Q0@J.de.Boyne.Pollard.localhost> |
| In reply to | #649 |
>> I took a look at the glibc implementation of qsort(). It does use >> Quicksort, but with some tweaks. It picks the pivot using a >> median-of-three decision tree, it falls back to insertion sort for >> small segments, it uses an explicit stack rather than recursion, and >> it always handles the larger partition first. >> > Odd, in order to reduce actual recursion (and do tail recursion > instead), and to keep locality of reference tight, I'd handle the > smaller part first were I to use an actual quicksort. > You've made me curious enough to revisit the code of my standard library's sorting function after many years. It does median-of-three and falls back to insertion sort (or even just a straight immediate swap for fewer than three elements). But, like M. Carmody, I pick the smaller portion to tail recurse on. This is what Robert Sedgewick does. All of these "tweaks" mentioned are discussed by Sedgewick, in fact.
[toc] | [prev] | [next] | [standalone]
| From | "robertwessel2@yahoo.com" <robertwessel2@yahoo.com> |
|---|---|
| Date | 2011-05-23 17:45 -0700 |
| Message-ID | <bb9329d4-1361-4fbe-a939-772c1f09da59@m10g2000yqd.googlegroups.com> |
| In reply to | #649 |
On May 23, 1:57 pm, Phil Carmody <thefatphil_demun...@yahoo.co.uk> wrote: > Keith Thompson <ks...@mib.org> writes: > > Keith Thompson <ks...@mib.org> writes: > > [...] > > > If I were designing a program that needs to sort arrays whose > > > contents are not under my control, I'd avoid using an algorithm > > > whose run-time behavior can vary tremendously depending on the > > > nature of the input -- not just because of the possibility of > > > malicious attacks, but because even random data could conceivably > > > cause the same problem. Even if the problem is unlikely to occur, > > > it's good to have one less thing to worry about. > > > > If this were difficult to do, I'd stop and consider whether it's > > > worth the effort, but it shouldn't be. Though a naive Quicksort > > > algorithm does suffer from this problem, my guess is that most, > > > perhaps all, library sorting algorithms avoid it, either by tweaking > > > Quicksort or by using a different algorithm. > > > On re-reading this, I realize that the sentence > > > If this were difficult to do, I'd stop and consider whether it's > > worth the effort, but it shouldn't be. > > > was unclear. I meant that it shouldn't be difficult to do, not > > that it shouldn't be worth the effort. > > > > A concrete question: Are there any existing C library implementations > > > of qsort() that are vulnerable to this kind of problem? > > > I took a look at the glibc implementation of qsort(). It does > > use Quicksort, but with some tweaks. It picks the pivot using a > > median-of-three decision tree, it falls back to insertion sort for > > small segments, it uses an explicit stack rather than recursion, > > and it always handles the larger partition first. > > Odd, in order to reduce actual recursion (and do tail recursion > instead), and to keep locality of reference tight, I'd handle the > smaller part first were I to use an actual quicksort. Not that I'd > do that, being more of a fan of heapsort in situations where I want > an acceptable worst-case big-Oh for reasons such as availability. The usual approach for the semi-recursive implementation is to recurse on the smaller partition, and then loop (or allow tail recursion, assuming your implementation language supports that) on the bigger one. If you do a fully iterative version (managing your own stack), you need to “push” the smaller partition last, so that you sort it first. If you do it the other way, you can't bound your stack size to log(N). A fully recursive implementation is stuck with order-N worst case stack requirements (no matter which order you process the partitions), unless you can guarantee tail recursion elimination. > > I don't know > > whether this completely avoids the worst-case N**2 behavior or not, > > but it should make it less likely to happen accidentally. > > Nope, reduces the constant, that's all. If the median is selected > from 3 random (i.e. unpredicatable to an attacker) elements, then > the worst case behaviour can not be forced, and you would average > to the theoretical average. But then you have to secure information > about your (P)RNG state. And producing large quantities of good random numbers with low overhead is much harder than the problem you wanted to solve in the first place.
[toc] | [prev] | [next] | [standalone]
| From | Rainer Weikusat <rweikusat@mssgmbh.com> |
|---|---|
| Date | 2011-05-24 11:43 +0100 |
| Message-ID | <87r57ojs40.fsf@sapphire.mobileactivedefense.com> |
| In reply to | #653 |
"robertwessel2@yahoo.com" <robertwessel2@yahoo.com> writes: [...] >>> I don't know whether this completely avoids the worst-case N**2 >>> behavior or not, but it should make it less likely to happen >>> accidentally. >> >> Nope, reduces the constant, that's all. If the median is selected >> from 3 random (i.e. unpredicatable to an attacker) elements, then >> the worst case behaviour can not be forced, and you would average >> to the theoretical average. But then you have to secure information >> about your (P)RNG state. > > And producing large quantities of good random numbers with low > overhead is much harder than the problem you wanted to solve in the > first place. In theory. In practice, all this takes is linking with OpenSSL, assuming that some source of good randomness will always be available/ nobody except the person who wrote the code will ever bother to check it with that much detail (especially, since the chances that anyone who is at least remoteley superior insofar job positions go both understands the issue and cares about it in absence of a pending customer lawsuit are extremly slim) and then go on a happy, four week holiday somewhere in the sun with the pleasant conviction that an inherently wrong solution for some problem can always be turned into something which gives a 'good enough' appearance of working for all practical purposes by making the implementation complicated enough to hide its deficiencies.
[toc] | [prev] | [next] | [standalone]
| From | "robertwessel2@yahoo.com" <robertwessel2@yahoo.com> |
|---|---|
| Date | 2011-05-24 10:58 -0700 |
| Message-ID | <d2f2fc3a-0405-4bef-b251-fa46e4adcc75@f15g2000yqe.googlegroups.com> |
| In reply to | #655 |
On May 24, 5:43 am, Rainer Weikusat <rweiku...@mssgmbh.com> wrote: > "robertwess...@yahoo.com" <robertwess...@yahoo.com> writes: > > [...] > > >>> I don't know whether this completely avoids the worst-case N**2 > >>> behavior or not, but it should make it less likely to happen > >>> accidentally. > > >> Nope, reduces the constant, that's all. If the median is selected > >> from 3 random (i.e. unpredicatable to an attacker) elements, then > >> the worst case behaviour can not be forced, and you would average > >> to the theoretical average. But then you have to secure information > >> about your (P)RNG state. > > > And producing large quantities of good random numbers with low > > overhead is much harder than the problem you wanted to solve in the > > first place. > > In theory. In practice, all this takes is linking with OpenSSL, > assuming that some source of good randomness will always be available/ > nobody except the person who wrote the code will ever bother to check > it with that much detail (especially, since the chances that anyone who > is at least remoteley superior insofar job positions go both > understands the issue and cares about it in absence of a pending > customer lawsuit are extremly slim) and then go on a happy, four week > holiday somewhere in the sun with the pleasant conviction that an > inherently wrong solution for some problem can always be turned > into something which gives a 'good enough' appearance of working for > all practical purposes by making the implementation complicated > enough to hide its deficiencies. Open SSL (or whichever crypto library is handy on your platform) will fairly easy produce a stream of high quality random bits. It will, however, have very high overhead. So much so that I’d expect a straight Heapsort to be faster, which would be simpler than the Quicksort implementation (just counting the sort part of the code). Poor quality “random” numbers are much easier to generate. Your point about an apparently good enough (which all too often equates to "no demonstrated fatal flaws"), but cheap, solution frequently satisfying the bosses, is of course, a general truth.
[toc] | [prev] | [next] | [standalone]
| From | Sherm Pendley <sherm.pendley@gmail.com> |
|---|---|
| Date | 2011-05-11 11:11 -0400 |
| Message-ID | <87boz9uvaw.fsf@sherm.shermpendley.com> |
| In reply to | #483 |
Michael Press <rubrum@pacbell.net> writes: > I cannot see myself ever calling bsearch(3). I will > call qsort(3). Note the existence of qsort_r. > Sometimes I'll write an insertion sort with binary > search. Sometimes I'll write a heapsort. This stuff > is not hard. It may not be hard, but it *is* boring and well-covered ground. I'd rather spend my time on wheels that haven't yet been invented. :-) sherm--
[toc] | [prev] | [next] | [standalone]
| From | Michael Press <rubrum@pacbell.net> |
|---|---|
| Date | 2011-05-11 19:48 -0700 |
| Message-ID | <rubrum-107C14.19482811052011@news.albasani.net> |
| In reply to | #531 |
In article <87boz9uvaw.fsf@sherm.shermpendley.com>, Sherm Pendley <sherm.pendley@gmail.com> wrote: > Michael Press <rubrum@pacbell.net> writes: > > > I cannot see myself ever calling bsearch(3). I will > > call qsort(3). Note the existence of qsort_r. > > Sometimes I'll write an insertion sort with binary > > search. Sometimes I'll write a heapsort. This stuff > > is not hard. > > It may not be hard, but it *is* boring and well-covered > ground. I'd rather spend my time on wheels that haven't > yet been invented. :-) I am easily amused. -- Michael Press
[toc] | [prev] | [next] | [standalone]
| From | Keith Thompson <kst-u@mib.org> |
|---|---|
| Date | 2011-05-09 16:22 -0700 |
| Message-ID | <ln1v07o3wc.fsf@nuthaus.mib.org> |
| In reply to | #459 |
Måns Rullgård <mans@mansr.com> writes:
> Joshua Maurice <joshuamaurice@gmail.com> writes:
>> On May 9, 3:05 pm, Michael Press <rub...@pacbell.net> wrote:
>>> There are good reasons to write it oneself. When I want
>>> a binary search I simply write it on the fly; and embed
>>> whatever I want to do with the search result right there.
>>>
>>> It takes as long or longer to write the interfaces to a
>>> library binary search as it does to write one that does
>>> exactly what I want.
>>
>> I politely disagree, and I must express my extreme disbelief at this
>> statement that you can write a good correct binary search algorithm
>> faster than you can use C++ std::map, or C++ std::lower_bound, et al.
>
> A binary search is roughly 10 lines of code. Writing one really doesn't
> take long.
In "Programming Pearls", Jon Bentley writes:
While the first binary search was published in 1946, the first
binary search that works correctly for all values of n did not
appear until 1962.
--
Keith Thompson (The_Other_Keith) kst-u@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
[toc] | [prev] | [next] | [standalone]
| From | Michael Press <rubrum@pacbell.net> |
|---|---|
| Date | 2011-05-09 21:25 -0700 |
| Message-ID | <rubrum-A5C291.21254709052011@news.albasani.net> |
| In reply to | #463 |
In article <ln1v07o3wc.fsf@nuthaus.mib.org>, Keith Thompson <kst-u@mib.org> wrote: > Måns Rullgård <mans@mansr.com> writes: > > Joshua Maurice <joshuamaurice@gmail.com> writes: > >> On May 9, 3:05 pm, Michael Press <rub...@pacbell.net> wrote: > >>> There are good reasons to write it oneself. When I want > >>> a binary search I simply write it on the fly; and embed > >>> whatever I want to do with the search result right there. > >>> > >>> It takes as long or longer to write the interfaces to a > >>> library binary search as it does to write one that does > >>> exactly what I want. > >> > >> I politely disagree, and I must express my extreme disbelief at this > >> statement that you can write a good correct binary search algorithm > >> faster than you can use C++ std::map, or C++ std::lower_bound, et al. > > > > A binary search is roughly 10 lines of code. Writing one really doesn't > > take long. > > In "Programming Pearls", Jon Bentley writes: > > While the first binary search was published in 1946, the first > binary search that works correctly for all values of n did not > appear until 1962. I've had sixteen years to get it right too. I feel sorry for those without the confidence to write their own binary search. -- Michael Press
[toc] | [prev] | [next] | [standalone]
| From | Seebs <usenet-nospam@seebs.net> |
|---|---|
| Date | 2011-05-10 17:28 +0000 |
| Message-ID | <slrnishl8g.v9t.usenet-nospam@guild.seebs.net> |
| In reply to | #466 |
On 2011-05-10, Michael Press <rubrum@pacbell.net> wrote: > I feel sorry for those without the confidence > to write their own binary search. I am pretty typo-prone. I'd rather not take any more chances than I have to. :) -s -- Copyright 2011, all wrongs reversed. Peter Seebach / usenet-nospam@seebs.net http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated! I am not speaking for my employer, although they do rent some of my opinions.
[toc] | [prev] | [next] | [standalone]
| From | Michael Press <rubrum@pacbell.net> |
|---|---|
| Date | 2011-05-09 17:11 -0700 |
| Message-ID | <rubrum-B22B70.17115409052011@news.albasani.net> |
| In reply to | #458 |
In article <2f33e674-b127-4c35-89b5-dcbf564f3aab@h36g2000pro.googlegroups.com>, Joshua Maurice <joshuamaurice@gmail.com> wrote: > On May 9, 3:05 pm, Michael Press <rub...@pacbell.net> wrote: > > There are good reasons to write it oneself. When I want > > a binary search I simply write it on the fly; and embed > > whatever I want to do with the search result right there. > > > > It takes as long or longer to write the interfaces to a > > library binary search as it does to write one that does > > exactly what I want. > > I politely disagree, and I must express my extreme disbelief at this > statement that you can write a good correct binary search algorithm > faster than you can use C++ std::map, or C++ std::lower_bound, et al. Does the library write your compare routine and unit test it for me? Does the library routine inline the code that examines the return and executed the action dependent on the return value? Does the library return a value in exactly the form I want? -- Michael Press
[toc] | [prev] | [next] | [standalone]
| From | Ian Collins <ian-news@hotmail.com> |
|---|---|
| Date | 2011-05-10 12:20 +1200 |
| Message-ID | <92reltF51pU8@mid.individual.net> |
| In reply to | #464 |
On 05/10/11 12:11 PM, Michael Press wrote: > In article > <2f33e674-b127-4c35-89b5-dcbf564f3aab@h36g2000pro.googlegroups.com>, > Joshua Maurice<joshuamaurice@gmail.com> wrote: > >> On May 9, 3:05 pm, Michael Press<rub...@pacbell.net> wrote: >>> There are good reasons to write it oneself. When I want >>> a binary search I simply write it on the fly; and embed >>> whatever I want to do with the search result right there. >>> >>> It takes as long or longer to write the interfaces to a >>> library binary search as it does to write one that does >>> exactly what I want. >> >> I politely disagree, and I must express my extreme disbelief at this >> statement that you can write a good correct binary search algorithm >> faster than you can use C++ std::map, or C++ std::lower_bound, et al. > > Does the library write your compare routine > and unit test it for me? If it has to be written, you have to write and test the compare routine whether you use a library for the search or not. > Does the library > routine inline the code that examines the > return and executed the action dependent on > the return value? That's the compiler's job, not the library's. > Does the library return > a value in exactly the form I want? How many forms of true and false are there? -- Ian Collins
[toc] | [prev] | [next] | [standalone]
| From | pete <pfiland@mindspring.com> |
|---|---|
| Date | 2011-05-10 03:53 -0400 |
| Message-ID | <4DC8EEED.139F@mindspring.com> |
| In reply to | #465 |
Ian Collins wrote: > > On 05/10/11 12:11 PM, Michael Press wrote: > > In article > > <2f33e674-b127-4c35-89b5-dcbf564f3aab@h36g2000pro.googlegroups.com>, > > Joshua Maurice<joshuamaurice@gmail.com> wrote: > > > >> On May 9, 3:05 pm, Michael Press<rub...@pacbell.net> wrote: > >>> There are good reasons to write it oneself. When I want > >>> a binary search I simply write it on the fly; and embed > >>> whatever I want to do with the search result right there. > >>> > >>> It takes as long or longer to write the interfaces to a > >>> library binary search as it does to write one that does > >>> exactly what I want. > >> > >> I politely disagree, > >> and I must express my extreme disbelief at this > >> statement that you can write a good correct binary search algorithm > >> faster than you can use C++ std::map, > >> or C++ std::lower_bound, et al. I can write a good binary search algorithm faster than I can use C++ std::map, or C++ std::lower_bound, et al, because I don't know C++. > > Does the library write your compare routine > > and unit test it for me? > > If it has to be written, > you have to write and test the compare routine > whether you use a library for the search or not. > > > Does the library > > routine inline the code that examines the > > return and executed the action dependent on > > the return value? > > That's the compiler's job, not the library's. > > > Does the library return > > a value in exactly the form I want? > > How many forms of true and false are there? bsearch either returns NULL or returns a pointer to an element of an array. It is also possible to want a binary search which returns a pointer to the first occurance in the array or to want a binary search which returns a pointer to the last occurance in the array. -- pete
[toc] | [prev] | [next] | [standalone]
Page 9 of 14 — ← Prev page 1 … 7 8 [9] 10 11 … 14 Next page →
Back to top | Article view | comp.unix.programmer
csiph-web