Re: Port range option in bind-address implemented?
Micah Cowan wrote: Yes, that appears to work quite well, as long as we seed it right; starting with a consistent Xâ‚€ would be just as bad as trying them sequentially, and choosing something that does not change several times a second (such as time()) still makes it likely that multiple invocations will choose the same first port. Probably, /dev/random as first choice, falling back to by gettimeofday() where that's available. I don't know what Windows would use. QueryPerformanceCounter, if it seems trustworthy (i.e. != 0), which might be what Hrvoje pointed out. Otherwise the UUID generator is theoretically sufficient (and there is always getpid() which can be used to salt time... which is likely what the UUID generator does, anyway). -- Matthew Five is right out! -- Cleric (from Monty Python's Quest for the Holy Grail)
Re: Port range option in bind-address implemented?
Micah Cowan [EMAIL PROTECTED] writes: Yes, that appears to work quite well, as long as we seed it right; starting with a consistent X₀ would be just as bad as trying them sequentially, and choosing something that does not change several times a second (such as time()) still makes it likely that multiple invocations will choose the same first port. Probably, /dev/random as first choice, falling back to by gettimeofday() where that's available. I don't know what Windows would use. Wget already contains high-resolution timer code for Windows; see src/ptimer.c.
Re: Port range option in bind-address implemented?
-BEGIN PGP SIGNED MESSAGE- Hash: SHA256 Tony Godshall wrote: On 10/17/07, Tony Godshall [EMAIL PROTECTED] wrote: On 10/17/07, Micah Cowan [EMAIL PROTECTED] wrote: -BEGIN PGP SIGNED MESSAGE- Hash: SHA256 Tony Godshall wrote: Well, I'm don't have much to say about about the other points but one certainly does not need to keep an array for something like this- with the classic pseudorandom shuffle algorithm you only need to keep a count of the ones visited. Shall I pull out my Knuth? That... only applies if you actually keep a _queue_ around, of all the ports that you plan to try, and shuffle it. Surely that's more waste (65,535 shorts, versus 65,535 _bits_), not less? ...We're not shuffling, here, we're choosing. No, the point was that with a relative prime or two you can walk in a pseudorandom pattern though, hitting each point only once needing no array at all. Donald E. Knuth, The Art of Computer Programming, Volume 2, 3rd Edition, pp. 17-19 For the record, this is not what pseudo-random shuffle means to me: for instance, http://en.wikipedia.org/wiki/Fisher-Yates_shuffle (aka Knuth shuffle), which does in fact require an in-memory set to be permuted. Yes, that appears to work quite well, as long as we seed it right; starting with a consistent X₀ would be just as bad as trying them sequentially, and choosing something that does not change several times a second (such as time()) still makes it likely that multiple invocations will choose the same first port. Probably, /dev/random as first choice, falling back to by gettimeofday() where that's available. I don't know what Windows would use. We could probably use time() as a last resort, though I'm not crazy about it; maybe it'd be better to fail to support port ranges if there's not a decent seed available, and support exact port specifications. Thanks for the suggestion, Tony. - -- Micah J. Cowan Programmer, musician, typesetting enthusiast, gamer... http://micah.cowan.name/ -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.6 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFHF9b37M8hyUobTrERCCI2AKCSbpAs60wVZGvnOQN3y44HF64wegCgjYxo Nczvd/z7HVWMH0FfN/zWe28= =YID8 -END PGP SIGNATURE-
Re: Port range option in bind-address implemented?
On 10/18/07, Micah Cowan [EMAIL PROTECTED] wrote: -BEGIN PGP SIGNED MESSAGE- Hash: SHA256 Tony Godshall wrote: On 10/17/07, Tony Godshall [EMAIL PROTECTED] wrote: On 10/17/07, Micah Cowan [EMAIL PROTECTED] wrote: -BEGIN PGP SIGNED MESSAGE- Hash: SHA256 Tony Godshall wrote: Well, I'm don't have much to say about about the other points but one certainly does not need to keep an array for something like this- with the classic pseudorandom shuffle algorithm you only need to keep a count of the ones visited. Shall I pull out my Knuth? That... only applies if you actually keep a _queue_ around, of all the ports that you plan to try, and shuffle it. Surely that's more waste (65,535 shorts, versus 65,535 _bits_), not less? ...We're not shuffling, here, we're choosing. No, the point was that with a relative prime or two you can walk in a pseudorandom pattern though, hitting each point only once needing no array at all. Donald E. Knuth, The Art of Computer Programming, Volume 2, 3rd Edition, pp. 17-19 For the record, this is not what pseudo-random shuffle means to me: for instance, http://en.wikipedia.org/wiki/Fisher-Yates_shuffle (aka Knuth shuffle), which does in fact require an in-memory set to be permuted. Yeah, well, it's been 23 years since I took Data Structures, so sue me. And the shuffle you refer to is an attempt at actual randomness, whereas what I am talking about is explicitly a function of its *pseudo*-randomness- it's taking advantage of a characteristic (defect?) of an earlier attempt at real randomness. Yes, that appears to work quite well, as long as we seed it right; starting with a consistent X₀ would be just as bad as trying them sequentially, and choosing something that does not change several times a second (such as time()) still makes it likely that multiple invocations will choose the same first port. Probably, /dev/random as first choice, falling back to by gettimeofday() where that's available. I don't know what Windows would use. We could probably use time() as a last resort, though I'm not crazy about it; maybe it'd be better to fail to support port ranges if there's not a decent seed available, and support exact port specifications. Since implementation for 2^n is relatively easy, I think people usually write the algorithm to up to twice as many numbers as required and then skip if out of range. You know, I bet picking randomly and nonrepetetively from a range is a common enough task that it's in one of the standard libraries. If not, it probably should be. Thanks for the suggestion, Tony. If I have a though, I share. Too much sometimes ;-) or so my wife tells me. Tony
Port range option in bind-address implemented?
Greetings, Was the feature being discussed here http://www.mail-archive.com/wget@sunsite.dk/msg05546.html and here http://www.mail-archive.com/wget@sunsite.dk/msg05577.html ever get implemented? In other words, is it possible to do: wget --bind-address=1.2.3.4:2000-3000 http://... From trying it out and looking briefly at the code, it would appear it is not, but wanted to make sure. If that is the case, does anyone still have the old patch available, or has a similar new one? Thank you, and please cc: me on the replies directly, I'm not on the list. -Oleg
Re: Port range option in bind-address implemented?
-BEGIN PGP SIGNED MESSAGE- Hash: SHA256 Oleg Ace wrote: Greetings, Was the feature being discussed here http://www.mail-archive.com/wget@sunsite.dk/msg05546.html and here http://www.mail-archive.com/wget@sunsite.dk/msg05577.html ever get implemented? In other words, is it possible to do: wget --bind-address=1.2.3.4:2000-3000 http://... From trying it out and looking briefly at the code, it would appear it is not, but wanted to make sure. If that is the case, does anyone still have the old patch available, or has a similar new one? Looking at the threads you indicated, it appears that people were generally happy to include the feature, but were unhappy with the specific implementation from the patch: * parsing of --bind-address belongs in the getopt loop * sscanf() should be avoided for use in the parsing. * the ports should be chosen from that range at random, rather than sequentially, to address an issue pointed out by the Sockets FAQ. The third point above introduces its own problems: how many bind() attempts should we make before throwing in the towel? Or should we attempt every port in that range, keeping an 8k array of bits to track which ports we've tried already? Clearly, whatever approach we take will be _vastly_ less efficient/intelligent than the way the OS picks a port for us, and we'll need to point these limitations out in the documentation. I'm not going to write the code for this (at least not any time soon); if someone is interested enough to rewrite the patch to address these shortcomings, though, I'll be happy to include it, seeing as how it apparently met with Hrvoje's and Mauro's approval (and I see how it could be useful as well; though of course its primary use is probably to get around broken environments). I will submit a low-pri issue for it, in the meantime, in case someone sees it and wants to pick it up. :) - -- Micah J. Cowan Programmer, musician, typesetting enthusiast, gamer... http://micah.cowan.name/ -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.6 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFHFm3C7M8hyUobTrERCKYdAJwMSsemuOoWGmDFLxK8vAzxNlXQWQCfV89r 0gVv77+C2CIlI4lVULFLLC8= =xpu6 -END PGP SIGNATURE-
Re: Port range option in bind-address implemented?
On 10/17/07, Micah Cowan [EMAIL PROTECTED] wrote: -BEGIN PGP SIGNED MESSAGE- Hash: SHA256 Oleg Ace wrote: Greetings, Was the feature being discussed here http://www.mail-archive.com/wget@sunsite.dk/msg05546.html and here http://www.mail-archive.com/wget@sunsite.dk/msg05577.html ever get implemented? In other words, is it possible to do: wget --bind-address=1.2.3.4:2000-3000 http://... From trying it out and looking briefly at the code, it would appear it is not, but wanted to make sure. If that is the case, does anyone still have the old patch available, or has a similar new one? Looking at the threads you indicated, it appears that people were generally happy to include the feature, but were unhappy with the specific implementation from the patch: * parsing of --bind-address belongs in the getopt loop * sscanf() should be avoided for use in the parsing. * the ports should be chosen from that range at random, rather than sequentially, to address an issue pointed out by the Sockets FAQ. The third point above introduces its own problems: how many bind() attempts should we make before throwing in the towel? Or should we attempt every port in that range, keeping an 8k array of bits to track which ports we've tried already? Well, I'm don't have much to say about about the other points but one certainly does not need to keep an array for something like this- with the classic pseudorandom shuffle algorithm you only need to keep a count of the ones visited. Shall I pull out my Knuth? Clearly, whatever approach we take will be _vastly_ less efficient/intelligent than the way the OS picks a port for us, and we'll need to point these limitations out in the documentation. I'm not going to write the code for this (at least not any time soon); if someone is interested enough to rewrite the patch to address these shortcomings, though, I'll be happy to include it, seeing as how it apparently met with Hrvoje's and Mauro's approval (and I see how it could be useful as well; though of course its primary use is probably to get around broken environments). I will submit a low-pri issue for it, in the meantime, in case someone sees it and wants to pick it up. :) - -- Micah J. Cowan Programmer, musician, typesetting enthusiast, gamer... http://micah.cowan.name/ -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.6 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFHFm3C7M8hyUobTrERCKYdAJwMSsemuOoWGmDFLxK8vAzxNlXQWQCfV89r 0gVv77+C2CIlI4lVULFLLC8= =xpu6 -END PGP SIGNATURE- -- Best Regards. Please keep in touch.
Re: Port range option in bind-address implemented?
-BEGIN PGP SIGNED MESSAGE- Hash: SHA256 Tony Godshall wrote: Well, I'm don't have much to say about about the other points but one certainly does not need to keep an array for something like this- with the classic pseudorandom shuffle algorithm you only need to keep a count of the ones visited. Shall I pull out my Knuth? That... only applies if you actually keep a _queue_ around, of all the ports that you plan to try, and shuffle it. Surely that's more waste (65,535 shorts, versus 65,535 _bits_), not less? ...We're not shuffling, here, we're choosing. - -- Micah J. Cowan Programmer, musician, typesetting enthusiast, gamer... http://micah.cowan.name/ -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.6 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFHFn+z7M8hyUobTrERCD10AJ9YGkKdGx/fvvdmGs/kxImFNEABzwCeIfdc e0znB9IYTQVEjSwx9X3rWsY= =dmih -END PGP SIGNATURE-
Re: Port range option in bind-address implemented?
On 10/17/07, Micah Cowan [EMAIL PROTECTED] wrote: -BEGIN PGP SIGNED MESSAGE- Hash: SHA256 Tony Godshall wrote: Well, I'm don't have much to say about about the other points but one certainly does not need to keep an array for something like this- with the classic pseudorandom shuffle algorithm you only need to keep a count of the ones visited. Shall I pull out my Knuth? That... only applies if you actually keep a _queue_ around, of all the ports that you plan to try, and shuffle it. Surely that's more waste (65,535 shorts, versus 65,535 _bits_), not less? ...We're not shuffling, here, we're choosing. No, the point was that with a relative prime or two you can walk in a pseudorandom pattern though, hitting each point only once needing no array at all.
Re: Port range option in bind-address implemented?
On 10/17/07, Tony Godshall [EMAIL PROTECTED] wrote: On 10/17/07, Micah Cowan [EMAIL PROTECTED] wrote: -BEGIN PGP SIGNED MESSAGE- Hash: SHA256 Tony Godshall wrote: Well, I'm don't have much to say about about the other points but one certainly does not need to keep an array for something like this- with the classic pseudorandom shuffle algorithm you only need to keep a count of the ones visited. Shall I pull out my Knuth? That... only applies if you actually keep a _queue_ around, of all the ports that you plan to try, and shuffle it. Surely that's more waste (65,535 shorts, versus 65,535 _bits_), not less? ...We're not shuffling, here, we're choosing. No, the point was that with a relative prime or two you can walk in a pseudorandom pattern though, hitting each point only once needing no array at all. Donald E. Knuth, The Art of Computer Programming, Volume 2, 3rd Edition, pp. 17-19 -- Best Regards. Please keep in touch.
Re: Port range option in bind-address implemented?
On 10/17/07, Tony Godshall [EMAIL PROTECTED] wrote: On 10/17/07, Tony Godshall [EMAIL PROTECTED] wrote: On 10/17/07, Micah Cowan [EMAIL PROTECTED] wrote: -BEGIN PGP SIGNED MESSAGE- Hash: SHA256 Tony Godshall wrote: Well, I'm don't have much to say about about the other points but one certainly does not need to keep an array for something like this- with the classic pseudorandom shuffle algorithm you only need to keep a count of the ones visited. Shall I pull out my Knuth? That... only applies if you actually keep a _queue_ around, of all the ports that you plan to try, and shuffle it. Surely that's more waste (65,535 shorts, versus 65,535 _bits_), not less? ...We're not shuffling, here, we're choosing. No, the point was that with a relative prime or two you can walk in a pseudorandom pattern though, hitting each point only once needing no array at all. Donald E. Knuth, The Art of Computer Programming, Volume 2, 3rd Edition, pp. 17-19 ...and probably closer at hand... http://en.wikipedia.org/wiki/Linear_congruential_generator TG
