Re: PROBLEM FOUND (sort of): Re: lpr: order of print requests
On Wed, 3 May 2000, Garance A Drosihn wrote: > With the update I made, the sort will be stable because the two > filenames will not be equal. Please try the update at: > > http://www.freebsd.org/cgi/query-pr.cgi?pr=18361 > [PATCH] Fix for queue-ordering problem in lpr/lpd/lpq > > or pick up the update from: > ftp://freefour.acs.rpi.edu/pub/bsdlpr/lpr_qfix.diff This is excellent. I beat on it with my test-case and it works fine. Could someone please commit this to 5-CURRENT, 4-STABLE and even 3-STABLE? I imagine even 2.2-STABLE users wouldn't mind. -- Chris Dillon - [EMAIL PROTECTED] - [EMAIL PROTECTED] FreeBSD: The fastest and most stable server OS on the planet. For Intel x86 and Alpha architectures. ( http://www.freebsd.org ) To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-hackers" in the body of the message
Re: PROBLEM FOUND (sort of): Re: lpr: order of print requests
At 7:56 AM -0500 5/3/00, Chris Dillon wrote: >That isn't the problem. You can sleep as much as you want between >submitting the print jobs and the job order still gets munged. >Even a job that at one time had #1 rank gets inverted and ends up >with the lowest rank. He's saying that you could work around the problem if the EARLIER jobs had used a sleep between them, ie, so they do not have the same last-mod time. If they do not match, then the order will not get confused when later jobs arrive. What he is saying is correct, even though it is not very useful in practice... (his work-around would have helped Lorenzo, but it is not practical for your samba-server example). >It appears that qsort() is the culprit. In fact, here is an >excerpt from the manpage: > >The functions qsort() and heapsort() are not stable, that is, >if two members compare as equal, their order in the sorted >array is undefined. The function mergesort() is stable. > With the update I made, the sort will be stable because the two filenames will not be equal. Please try the update at: http://www.freebsd.org/cgi/query-pr.cgi?pr=18361 [PATCH] Fix for queue-ordering problem in lpr/lpd/lpq or pick up the update from: ftp://freefour.acs.rpi.edu/pub/bsdlpr/lpr_qfix.diff --- Garance Alistair Drosehn = [EMAIL PROTECTED] Senior Systems Programmer or [EMAIL PROTECTED] Rensselaer Polytechnic Institute To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-hackers" in the body of the message
Re: PROBLEM FOUND (sort of): Re: lpr: order of print requests
In the last episode (May 03), Chris Dillon said: > On Tue, 2 May 2000, Dan Nelson wrote: > > Aha. Yes, it _does_ do FIFO, but if you look at the source, the > > queue sorting routine simply sorts on stat(mtime) of the queue > > file, so jobs submitted in the same second will sort randomly. A > > quick fix would be to sleep for 1 second between "lpr" calls. > > That isn't the problem. You can sleep as much as you want between > submitting the print jobs and the job order still gets munged. Even If this is the case, then using mtime at all is wrong. You sure waiting 1 second between submissions doesn't work? > a job that at one time had #1 rank gets inverted and ends up with the > lowest rank. I even modified common.c (a shot in the dark, I had no > idea what I was doing, really) to check for modtime with > st_mtimespec.tv_nsec for nsec modtime resolution, and that didn't > change the behaviour any. I checked, and fstat() always puts zeros in the nsec fields, either because ffs doesn't store them, or for some other reason. > It appears that qsort() is the culprit. In fact, here is an excerpt > from the manpage: > > The functions qsort() and heapsort() are not stable, that is, if > two mem- bers compare as equal, their order in the sorted array > is undefined. The function mergesort() is stable. This doesn't help, since you can't guarantee that the files are in order in the directory, either. I think someone posted a better solution, which would be sorting by mtime, and when mtime is identical, sort by job number in the filename. You can't simply sort by filename because that would break "lpc topq". -- Dan Nelson [EMAIL PROTECTED] To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-hackers" in the body of the message
Re: PROBLEM FOUND (sort of): Re: lpr: order of print requests
On Tue, 2 May 2000, Dan Nelson wrote: > In the last episode (May 02), Chris Dillon said: > > On Tue, 2 May 2000, Konrad Heuer wrote: > > > Hmm, I've never seen such a strange behaviour. Lpd should do FIFO. > > > Could you give some more infos about your environment (os release, > > > input filter program, printer type)? > > Aha. Yes, it _does_ do FIFO, but if you look at the source, the queue > sorting routine simply sorts on stat(mtime) of the queue file, so jobs > submitted in the same second will sort randomly. A quick fix would be > to sleep for 1 second between "lpr" calls. That isn't the problem. You can sleep as much as you want between submitting the print jobs and the job order still gets munged. Even a job that at one time had #1 rank gets inverted and ends up with the lowest rank. I even modified common.c (a shot in the dark, I had no idea what I was doing, really) to check for modtime with st_mtimespec.tv_nsec for nsec modtime resolution, and that didn't change the behaviour any. It appears that qsort() is the culprit. In fact, here is an excerpt from the manpage: The functions qsort() and heapsort() are not stable, that is, if two mem- bers compare as equal, their order in the sorted array is undefined. The function mergesort() is stable. You would think that with nsec modtime resolution, the chance of two jobs having equal sort criteria is slim to none, so most likely I didn't do the modtime change correctly. I wonder if we can work mergesort() in there somehow. I also notice that the job numbers assigned to the jobs are sequential, so maybe that can be a sort criteria as well. I'm just being a detective, but I'm not a C programmer, so don't look at me. :-) -- Chris Dillon - [EMAIL PROTECTED] - [EMAIL PROTECTED] FreeBSD: The fastest and most stable server OS on the planet. For Intel x86 and Alpha architectures. ( http://www.freebsd.org ) To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-hackers" in the body of the message
Re: PROBLEM FOUND: Re: lpr: order of print requests
At 8:37 PM -0400 5/2/00, Garance A Drosihn wrote: >This should not break anything. I will write up an update which >does this, unless someone thinks it is a BadIdea(tm) for some reason. >Someone else would have to commit the change to the official source, >but at least Lorenzo could try that change and see if it helps his >situation. Well, I waited several whole minutes and no one complained, and I happen to be working on RPI's lpd right now, so I wrote up an update for this. Please see http://www.freebsd.org/cgi/query-pr.cgi?pr=18361 [PATCH] Fix for queue-ordering problem in lpr/lpd/lpq or pick up the update from: ftp://freefour.acs.rpi.edu/pub/bsdlpr/lpr_qfix.diff and test it out. It seems to work fine for me. If no problems come up, please submit a follow-up to the PR so people know it has been tested. --- Garance Alistair Drosehn = [EMAIL PROTECTED] Senior Systems Programmer or [EMAIL PROTECTED] Rensselaer Polytechnic Institute To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-hackers" in the body of the message
Re: PROBLEM FOUND (sort of): Re: lpr: order of print requests
At 5:47 PM -0500 5/2/00, Dan Nelson wrote: >In the last episode (May 02), Chris Dillon said: > > On Tue, 2 May 2000, Konrad Heuer wrote: > > > Hmm, I've never seen such a strange behaviour. Lpd should do FIFO. > > > Could you give some more infos about your environment (os release, > > > input filter program, printer type)? > >Aha. Yes, it _does_ do FIFO, but if you look at the source, the queue >sorting routine simply sorts on stat(mtime) of the queue file, so jobs >submitted in the same second will sort randomly. A quick fix would be >to sleep for 1 second between "lpr" calls. I would call that more of a "workaround" than a "fix"... :-) For the example situation that Lorenzo is talking about, a quick fix to lpr might be to change the compar() routine in common_source/common.c. The code should probably check for the case where two files have the same last-modification time (to the degree of accuracy that stat() can tell the last-mod time), and if they match then the routine should sort the cf files based on the file-name. That means 'cfA001some.host.name' would always come before 'cfA002some.host.name', so it solves the problem when jobs area all coming from the same hostname, except for the case where the jobid wraps around from '999' to '000'. Probably could handle that case easily enough, too, with a little extra thought. This should not break anything. I will write up an update which does this, unless someone thinks it is a BadIdea(tm) for some reason. Someone else would have to commit the change to the official source, but at least Lorenzo could try that change and see if it helps his situation. Given the example he gave in a different message, I am not completely convinced that this is the problem he is seeing. Still, this change does seem like a good idea to do. --- Garance Alistair Drosehn = [EMAIL PROTECTED] Senior Systems Programmer or [EMAIL PROTECTED] Rensselaer Polytechnic Institute To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-hackers" in the body of the message
Re: lpr: order of print requests
At 2:09 PM -0600 5/1/00, Warner Losh wrote: >LPR queues up the reuqests and prints them in order smallest to >largest to reduce the average wait time for a job at the expense of >having a larger standard deviation in the wait times for jobs. Maybe >this is what you are running into. I don't know if there's a way to >disable this behavior or not. At least that's what I recall lpd doing >years ago when I ran a unix lab in school. I didn't go check the code >to see if it still did that or not. FreeBSD's lpr, as it ships, does not do queue reordering based on size. It is probably best that it remain this way. In the case of postscript jobs, for instance, reordering a queue based on the byte-size of the postscript job is pretty pointless. You can have a short job which takes a long time to print, or a long job which pretty much flies right through the queue. The byte-size of the postscript job does not accurately indicate how long it will take to plot. Postscript is a language. Saying which job will print faster is like claiming you can tell which C-program will execute in less time based on the byte-size of the C source files. I am sure that many sites would change lpr's behavior to implement some kind of prioritization based on file size or file type, but lpr as exists in freebsd source is FIFO (assuming no one does an 'lpc topq' to explicitly change that order...). Looking at the source code (the getq() and compar() routines in lpr/common_source/common.c), it is clear that it only checks the last-modification time of the cf files for each job. 'lpc topq' works by altering those last-modification timestamps. --- Garance Alistair Drosehn = [EMAIL PROTECTED] Senior Systems Programmer or [EMAIL PROTECTED] Rensselaer Polytechnic Institute To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-hackers" in the body of the message
Re: PROBLEM FOUND (sort of): Re: lpr: order of print requests
In the last episode (May 02), Chris Dillon said: > On Tue, 2 May 2000, Konrad Heuer wrote: > > Hmm, I've never seen such a strange behaviour. Lpd should do FIFO. > > Could you give some more infos about your environment (os release, > > input filter program, printer type)? Aha. Yes, it _does_ do FIFO, but if you look at the source, the queue sorting routine simply sorts on stat(mtime) of the queue file, so jobs submitted in the same second will sort randomly. A quick fix would be to sleep for 1 second between "lpr" calls. -- Dan Nelson [EMAIL PROTECTED] To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-hackers" in the body of the message
Re: PROBLEM FOUND (sort of): Re: lpr: order of print requests
I'd bet it does, quicksort is not a stable sort and all of your print requests are the same length. -Ira To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-hackers" in the body of the message
PROBLEM FOUND (sort of): Re: lpr: order of print requests
On Tue, 2 May 2000, Konrad Heuer wrote: > > On Tue, 2 May 2000, Lorenzo Iania wrote: > > > Warren Losh wrote: > > > > > LPR queues up the reuqests and prints them in order smallest to > > > largest to reduce the average wait time for a job at the expense of > > > having a larger standard deviation in the wait times for jobs. Maybe > > > this is what you are running into. I don't know if there's a way to > > > disable this behavior or not. At least that's what I recall lpd doing > > > years ago when I ran a unix lab in school. I didn't go check the code > > > to see if it still did that or not. > > > > > > Warner > > > > > > > I think you're right, because the process that generates the requests is > > only one. It consecutively opens pipes to lpr and then closes them. In > > effect it builds invoices from delivery documents and the printed numbers of > > invoices is effectively out of order, while the requests are ordered by > > number of invoice. Each pipe is opened and closed: so the processes are not > > concurrent: one begins after the other has finished. > > So, is there a way to disable this strange behavior? > > Hmm, I've never seen such a strange behaviour. Lpd should do FIFO. Could > you give some more infos about your environment (os release, input filter > program, printer type)? I had the same problem when I used Samba and a FreeBSD box as an intermediary print queue to a networked laser printer for some Win95 boxes. Needless to say, the secretaries didn't like the fact that all of the checks they printed were out of order on numbered check stock. :-( This is definately a bug, probably in the queue sort routine in usr.sbin/lpr/common_source/common.c. I'm no good at C programming, or I'd take a shot at finding the exact culprit and fixing it myself. I'm on 4.0-STABLE, and here is what I can produce: # lpq -a # for foo in 1 2 3 4 5 6 7 8 9 10; do echo "$foo" | lpr -Praw; done # lpq -a raw: Warning: raw is down: printing disabled Warning: no daemon present Rank Owner Job Files Total Size 1stroot 41 (standard input) 3 bytes 2ndroot 33 (standard input) 2 bytes 3rdroot 34 (standard input) 2 bytes 4throot 35 (standard input) 2 bytes 5throot 36 (standard input) 2 bytes 6throot 37 (standard input) 2 bytes 7throot 38 (standard input) 2 bytes 8throot 39 (standard input) 2 bytes 9throot 40 (standard input) 2 bytes 10th root 32 (standard input) 2 bytes Notice the rank and job numbers, and that jobs 32 and 41 are swapped. Looking at the raw job data in the spool directory verifies that each sequential job is being placed into the queue with a correct sequential job number. Investigating further, this happens: Place just six jobs in the queue, and things are peachy: # lpq -a raw: Warning: raw is down: printing disabled Warning: no daemon present Rank Owner Job Files Total Size 1stroot 79 (standard input) 2 bytes 2ndroot 80 (standard input) 2 bytes 3rdroot 81 (standard input) 2 bytes 4throot 82 (standard input) 2 bytes 5throot 83 (standard input) 2 bytes 6throot 84 (standard input) 2 bytes Add a seventh job and the odd sorting behaviour happens: # lpq -a raw: Warning: raw is down: printing disabled Warning: no daemon present Rank Owner Job Files Total Size 1stroot 82 (standard input) 2 bytes 2ndroot 80 (standard input) 2 bytes 3rdroot 81 (standard input) 2 bytes 4throot 79 (standard input) 2 bytes 5throot 83 (standard input) 2 bytes 6throot 84 (standard input) 2 bytes 7throot 85 (standard input) 2 bytes The print queue is sorted by qsort(), so this wouldn't have anything to do with the magic number "7" I see in lib/libc/stdlib/qsort.c, would it? (ignore me... its probably just a coincidence) :-) -- Chris Dillon - [EMAIL PROTECTED] - [EMAIL PROTECTED] FreeBSD: The fastest and most stable server OS on the planet. For Intel x86 and Alpha architectures. ( http://www.freebsd.org ) To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-hackers" in the body of the message
Re: lpr: order of print requests
I don't know if I make any strange mistake, but I
have done the following simple thing.
File p.c :
#include
FILE
*fp
;
main(){register int
i ;
for
(i=0;i<1000;i++)
{ fp=popen("lpr
-Plp","w"); fprintf(fp,"Richiesta
N. %d\n",i);
pclose(fp);
}}
then
cc -o p p.c
./p
the result of lpq after this is:
waiting for lp to become ready
(offline?)Rank Owner Job
Files
Total Size1st root
33 (standard
input)
15 bytes2nd root
30 (standard
input)
15 bytes3rd root
35 (standard
input)
15 bytes4th root
36 (standard
input)
15 bytes5th root
29 (standard
input)
15 bytes6th root
31 (standard
input)
15 bytes7th root
37 (standard
input)
15 bytes8th root
38 (standard
input)
15 bytes9th root
39 (standard
input)
16 bytes10th root
40 (standard
input)
16 bytes11th root
41 (standard
input)
16 bytes12th root
42 (standard
input)
16 bytes13th root
32 (standard
input)
15 bytes14th root
34 (standard
input)
15 bytes15th root
56 (standard
input)
16 bytes16th root
57 (standard
input)
16 bytes17th root
43 (standard
input)
16 bytes
etc
As you can see, the first on the queue is Job 33,
while the second is 30 and so on
The sizes are irrilevant because they are the
same.
For this reason, and for similar problems, it is
desiderable that the order of the requests is the same. I think that must be a
chance to respect the order of the requests to avoid situations like
this.
Thanks.
Re: lpr: order of print requests
Submitting the files with a single command should prevent reordering. lpc's topq command can be used to move a job to the top of the queue. Printing small jobs first is a desirable feature. Too often I've found a dozen people waiting while large jobs tied up the printers and that user wasn't present. I haven't looked at the code, but was told it took both size and submission time into consideration so that even large jobs would eventually print. If sending to a private printer, who does the print order matter? Are you trying to use forms? > I think you're right, because the process that generates the requests > is only one. It consecutively opens pipes to lpr and then closes > them. In effect it builds invoices from delivery documents and the > printed numbers of invoices is effectively out of order, while the > requests are ordered by number of invoice. Each pipe is opened and > closed: so the processes are not concurrent: one begins after the > other has finished. So, is there a way to disable this strange > behavior? > > Thanks. >> LPR queues up the reuqests and prints them in order smallest to >> largest to reduce the average wait time for a job at the expense of >> having a larger standard deviation in the wait times for jobs. Maybe >> this is what you are running into. I don't know if there's a way to >> disable this behavior or not. At least that's what I recall lpd doing >> years ago when I ran a unix lab in school. I didn't go check the code >> to see if it still did that or not. >> >> Warner To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-hackers" in the body of the message
Re: lpr: order of print requests
Konrad Heuer wrote
> Hmm, I've never seen such a strange behaviour.
Lpd should do FIFO. Could> you give some more infos about your
environment (os release, input filter> program, printer
type)?
Yes, I think it's a very strange
behaviour.
In effect in the file
/usr/src/usr.sbin/lpr/common_source/common.c there is:
.
/* * Scan the current directory and make a
list of daemon files sorted by * creation time. * Return the
number of entries and a pointer to the list. */intgetq(pp,
namelist) const struct printer
*pp; struct queue
*(*namelist[]);{.
However I had the problem in more than one
installation of the os from 2.2.7 to 3.4.
The printers are used in a very simple
way,
...
lp|local line
printer:\
:sh:sf:mx#0:\
:lp=/dev/lpt0:sd=/usr/spool/output/lpd:lf=/var/log/lpd-errs:
but the order is wrong. The problem occur when the
number of consecutive requests grows, i. e. when I have to print requests from 1
to 100 (from tha same process), the first 40 are in the right order, then are
printed those from 50 to 100 in the right order and at last those from 41 to
49.
All I do is simply open a pipe by a call to
fp=popen("lpr -Plp","a");
fprintf(fp,X);
.
..
.
fclose(fp);
The contents are almost the same for each request,
simply characters; I don't use any input filter. The printer is always a
character printer like IBM, EPSON ...
So I don't understand why this
happens.
Any suggestions??
Re: lpr: order of print requests
On Tue, 2 May 2000, Lorenzo Iania wrote: > Warren Losh wrote: > > > LPR queues up the reuqests and prints them in order smallest to > > largest to reduce the average wait time for a job at the expense of > > having a larger standard deviation in the wait times for jobs. Maybe > > this is what you are running into. I don't know if there's a way to > > disable this behavior or not. At least that's what I recall lpd doing > > years ago when I ran a unix lab in school. I didn't go check the code > > to see if it still did that or not. > > > > Warner > > > > I think you're right, because the process that generates the requests is > only one. It consecutively opens pipes to lpr and then closes them. In > effect it builds invoices from delivery documents and the printed numbers of > invoices is effectively out of order, while the requests are ordered by > number of invoice. Each pipe is opened and closed: so the processes are not > concurrent: one begins after the other has finished. > So, is there a way to disable this strange behavior? Hmm, I've never seen such a strange behaviour. Lpd should do FIFO. Could you give some more infos about your environment (os release, input filter program, printer type)? Regards Konrad HeuerPersonal Bookmarks: Gesellschaft für wissenschaftliche Datenverarbeitung mbH GÖttingen http://www.freebsd.org Am Faßberg, D-37077 GÖttingen http://www.daemonnews.org Deutschland (Germany) [EMAIL PROTECTED] To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-hackers" in the body of the message
Re: lpr: order of print requests
Warren Losh wrote: > LPR queues up the reuqests and prints them in order smallest to > largest to reduce the average wait time for a job at the expense of > having a larger standard deviation in the wait times for jobs. Maybe > this is what you are running into. I don't know if there's a way to > disable this behavior or not. At least that's what I recall lpd doing > years ago when I ran a unix lab in school. I didn't go check the code > to see if it still did that or not. > > Warner > I think you're right, because the process that generates the requests is only one. It consecutively opens pipes to lpr and then closes them. In effect it builds invoices from delivery documents and the printed numbers of invoices is effectively out of order, while the requests are ordered by number of invoice. Each pipe is opened and closed: so the processes are not concurrent: one begins after the other has finished. So, is there a way to disable this strange behavior? Thanks. To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-hackers" in the body of the message
Re: lpr: order of print requests
LPR queues up the reuqests and prints them in order smallest to largest to reduce the average wait time for a job at the expense of having a larger standard deviation in the wait times for jobs. Maybe this is what you are running into. I don't know if there's a way to disable this behavior or not. At least that's what I recall lpd doing years ago when I ran a unix lab in school. I didn't go check the code to see if it still did that or not. Warner To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-hackers" in the body of the message
Re: lpr: order of print requests
At 4:40 PM +0200 4/28/00, Lorenzo Iania wrote: >I have the following problem using lpr: >when the number of consecutive requests grow, they are not printed in the >same order. This happens on several versions from 2.2.7 to 3.4. All the >requests are printed, but the order is not the same of the requests. >Effectively the order is initially right, but then it fails and skips a >number of requests that are printer later. > >Why this happens? What can I do? Any suggestions?? I am not sure what you mean by "requests". Do you mean many 'lpr' commands from different users/hosts, or do you mean many files on a single 'lpr' command? If you mean many 'lpr' commands, are they coming in from many different hosts to some central print server? --- Garance Alistair Drosehn = [EMAIL PROTECTED] Senior Systems Programmer or [EMAIL PROTECTED] Rensselaer Polytechnic Institute To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-hackers" in the body of the message
