Re: serial port O_SYNC functionality in 2.4.5
Re: serial port O_SYNC func.. by "Stuart MacDonald"@conne > From: "James R Bruce" <[EMAIL PROTECTED]> > > As far as I can tell from observed operation and from perusing the > > code, O_SYNC doesn't seem to be supported by the serial driver in > > 2.4.5. Writes are forced as far as the serial.c's circular queue, but > > O_SYNC seems to be ignored from there on, so any application trying to > > do small synchronous writes to the serial port will end up backing it > > up PAGE_SIZE bytes rather than getting synchronous operation (which is > > incidentally what I was trying to do when I ran into this :). > > > > I'm unfamiliar with the serial driver so I'm not sure the right way to > > fix it is, but perhaps using a smaller value for WAKEUP_CHARS from > > drivers/char/serial.c when the port is opened with O_SYNC > > functionality might do the trick (i.e. 0 rather than 256). > > That might help, but it might not. That will only make sure that the > tx circular buffer is empty before getting another byte from the tty > layer into the buffer. The overall size of the circular buffer would have to be decreased too, but that's more of a hack to fix it now; Which I guess is what it comes to. > I think you will find that the real problem is that bytes written > into the hardware go into the fifo, and there's no general way to > tell when a byte has be actually txed; not in regular operation. This is not really a problem; 16 bytes of hardware buffering I can live with; at 19200 baud this is 7ms of lag. The 4096 byte software buffer causes 1706ms of lag; That *is* a problem. It's a bit like the difference between a hard disk drive's local buffer and the OS's (much larger) buffering. O_SYNC on a disk garuntees that the output has been flushed to the disk, but maybe not the physical medium. On a serial port, similar functionality would be to have output to pushed to the UART, but maybe not yet over the actual port. > You want to run the port in polled mode, which ensures one byte is > txed/rxed at a time. It's slow and cpu intensive though. setserial's > man page might have some info on this, also known as "low latency"; > meaning a specific byte has a low period of time between being rxed > and read/written and txed. The manpage seems to imply this would work, but it doesn't seem to affect the software buffering at all (I tried this yesterday). AFAICT from looking at the driver, the low_latency mode only applies to reading, not writing: tty_flip_buffer_push(tty) is the only place the latency flag is ever checked, and that is only called in receive_chars in serial.c. The application that caused this doesn't get any serial input whatsoever, so that won't (or at least shouldn't) get called. I changed WAKEUP_CHARS to 1 rather than 256 (0 would cause processes to hang forever, btw), and SERIAL_XMIT_SIZE to 16 rather than PAGE_SIZE. A proper solution would make this conditional on O_SYNC or low_latency or even a kernel option. Suggestions? - Jim Bruce - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
serial port O_SYNC functionality in 2.4.5
As far as I can tell from observed operation and from perusing the code, O_SYNC doesn't seem to be supported by the serial driver in 2.4.5. Writes are forced as far as the serial.c's circular queue, but O_SYNC seems to be ignored from there on, so any application trying to do small synchronous writes to the serial port will end up backing it up PAGE_SIZE bytes rather than getting synchronous operation (which is incidentally what I was trying to do when I ran into this :). I'm unfamiliar with the serial driver so I'm not sure the right way to fix it is, but perhaps using a smaller value for WAKEUP_CHARS from drivers/char/serial.c when the port is opened with O_SYNC functionality might do the trick (i.e. 0 rather than 256). Hopefully someone familiar with that part of the code please can tell me what should be done... or if a patch or configuration option can already get that functionality in another way. Thanks, Jim Bruce - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
serial port O_SYNC functionality in 2.4.5
As far as I can tell from observed operation and from perusing the code, O_SYNC doesn't seem to be supported by the serial driver in 2.4.5. Writes are forced as far as the serial.c's circular queue, but O_SYNC seems to be ignored from there on, so any application trying to do small synchronous writes to the serial port will end up backing it up PAGE_SIZE bytes rather than getting synchronous operation (which is incidentally what I was trying to do when I ran into this :). I'm unfamiliar with the serial driver so I'm not sure the right way to fix it is, but perhaps using a smaller value for WAKEUP_CHARS from drivers/char/serial.c when the port is opened with O_SYNC functionality might do the trick (i.e. 0 rather than 256). Hopefully someone familiar with that part of the code please can tell me what should be done... or if a patch or configuration option can already get that functionality in another way. Thanks, Jim Bruce - To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: serial port O_SYNC functionality in 2.4.5
Re: serial port O_SYNC func.. by Stuart MacDonald@conne From: James R Bruce [EMAIL PROTECTED] As far as I can tell from observed operation and from perusing the code, O_SYNC doesn't seem to be supported by the serial driver in 2.4.5. Writes are forced as far as the serial.c's circular queue, but O_SYNC seems to be ignored from there on, so any application trying to do small synchronous writes to the serial port will end up backing it up PAGE_SIZE bytes rather than getting synchronous operation (which is incidentally what I was trying to do when I ran into this :). I'm unfamiliar with the serial driver so I'm not sure the right way to fix it is, but perhaps using a smaller value for WAKEUP_CHARS from drivers/char/serial.c when the port is opened with O_SYNC functionality might do the trick (i.e. 0 rather than 256). That might help, but it might not. That will only make sure that the tx circular buffer is empty before getting another byte from the tty layer into the buffer. The overall size of the circular buffer would have to be decreased too, but that's more of a hack to fix it now; Which I guess is what it comes to. I think you will find that the real problem is that bytes written into the hardware go into the fifo, and there's no general way to tell when a byte has be actually txed; not in regular operation. This is not really a problem; 16 bytes of hardware buffering I can live with; at 19200 baud this is 7ms of lag. The 4096 byte software buffer causes 1706ms of lag; That *is* a problem. It's a bit like the difference between a hard disk drive's local buffer and the OS's (much larger) buffering. O_SYNC on a disk garuntees that the output has been flushed to the disk, but maybe not the physical medium. On a serial port, similar functionality would be to have output to pushed to the UART, but maybe not yet over the actual port. You want to run the port in polled mode, which ensures one byte is txed/rxed at a time. It's slow and cpu intensive though. setserial's man page might have some info on this, also known as low latency; meaning a specific byte has a low period of time between being rxed and read/written and txed. The manpage seems to imply this would work, but it doesn't seem to affect the software buffering at all (I tried this yesterday). AFAICT from looking at the driver, the low_latency mode only applies to reading, not writing: tty_flip_buffer_push(tty) is the only place the latency flag is ever checked, and that is only called in receive_chars in serial.c. The application that caused this doesn't get any serial input whatsoever, so that won't (or at least shouldn't) get called. I changed WAKEUP_CHARS to 1 rather than 256 (0 would cause processes to hang forever, btw), and SERIAL_XMIT_SIZE to 16 rather than PAGE_SIZE. A proper solution would make this conditional on O_SYNC or low_latency or even a kernel option. Suggestions? - Jim Bruce - To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: quicksort for linked list
Hi again. The latter half of my email seems to have been forgotten in the ensuing discussion, so I'll repost. For a linked list of any non-floating point data, radix sort is almost impossible to beat; it's iterative, fast (linear time for fixed size integers, worst case), can be stopped early for partial sorting, and has a pretty simple implementation. I've been using essentially the same radix sort implementation I posted before to sort 1000 item lists 60 times a second in a numerical application, and it barely shows up in the total time used when profiling. The other sorts I tried did not fare so well. I would much rather see this in a kernel modification than any merge/quick/heap sort implementations I've seen so far for linked lists. OTOH, this conversation seems to have wandered out of kernel-space anyway... - Jim Bruce (Examples at: http://www.cs.cmu.edu/~jbruce/sort.cc) 10-Mar-2001 Re: quicksort for linked list by David [EMAIL PROTECTED] > For modern machines, I'm not sure that quicksort on a linked list is > typically much cheaper than mergesort on a linked list. The > majority of the potential cost is likely to be in the pointer > chasing involved in bringing the lists into cache, and that will be > the same for both. Once the list is in cache, how much pointer > fiddling you do isn't so important. For lists that don't fit into > cache, the advantages of mergesort should become even greater if the > literature on tape and disk sorts applies (though multiway merges > rather than simple binary merges would be needed to minimize the > impact of memory latency). > > Given this, mergesort might be generally preferable to quicksort for > linked lists. But I haven't investigated this idea thoroughly. > (The trick described above for avoiding an explicit stack also works > for mergesort.) - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: quicksort for linked list
Hi again. The latter half of my email seems to have been forgotten in the ensuing discussion, so I'll repost. For a linked list of any non-floating point data, radix sort is almost impossible to beat; it's iterative, fast (linear time for fixed size integers, worst case), can be stopped early for partial sorting, and has a pretty simple implementation. I've been using essentially the same radix sort implementation I posted before to sort 1000 item lists 60 times a second in a numerical application, and it barely shows up in the total time used when profiling. The other sorts I tried did not fare so well. I would much rather see this in a kernel modification than any merge/quick/heap sort implementations I've seen so far for linked lists. OTOH, this conversation seems to have wandered out of kernel-space anyway... - Jim Bruce (Examples at: http://www.cs.cmu.edu/~jbruce/sort.cc) 10-Mar-2001 Re: quicksort for linked list by David [EMAIL PROTECTED] For modern machines, I'm not sure that quicksort on a linked list is typically much cheaper than mergesort on a linked list. The majority of the potential cost is likely to be in the pointer chasing involved in bringing the lists into cache, and that will be the same for both. Once the list is in cache, how much pointer fiddling you do isn't so important. For lists that don't fit into cache, the advantages of mergesort should become even greater if the literature on tape and disk sorts applies (though multiway merges rather than simple binary merges would be needed to minimize the impact of memory latency). Given this, mergesort might be generally preferable to quicksort for linked lists. But I haven't investigated this idea thoroughly. (The trick described above for avoiding an explicit stack also works for mergesort.) - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: quicksort for linked list
Quicksort works just fine on a linked list, as long as you broaden
your view beyond the common array-based implementations. See
"http://www.cs.cmu.edu/~jbruce/sort.cc" for an example, although I
would recommend using a radix sort for linked lists in most situations
(sorry for the C++, but it was handy...).
9-Mar-2001 Re: quicksort for linked list by Helge [EMAIL PROTECTED]
> Manoj Sontakke wrote:
> >
> > Hi
> > Sorry, these questions do not belog here but i could not find any
> > better place.
> >
> > 1. Is quicksort on doubly linked list is implemented anywhere? I need it
> > for sk_buff queues.
>
> I cannot see how the quicksort algorithm could work on a doubly
> linked list, as it relies on being able to look
> up elements directly as in an array.
>
> You can probably find algorithms for sorting a linked list, but
> it won't be quicksort.
It's quicksort as long as you do pivot/split, the array gymnastics
that most implementations do to avoid updating array elements isn't
really critical to its operation.
> 1. find out how many elements there are. (Count them if necessary)
> 2. Allocate a pointer array of this size.
> 3. fill the pointer array with pointers to list members.
> 4. quicksort the pointer array
> 5. Traverse the pointer array and set the links for each
>list member to point to next/previous element pointed
>to by the array. Now you have a sorted linked list!
I think a radix sort like the following would work better with about
the same (or less) storage, provided you're comparing ints (this is
for a kernel modification after all, right?). You just need to
determine the number of passes to cover all the bits in the numbers
you want to sort.
- Jim Bruce
#define RADIX_BITS 6
#define RADIX (1 << RADIX_BITS)
#define RADIX_MASK (RADIX - 1)
struct item *radix_sort(struct item *list,int passes)
// Sort list, largest first
{
struct item *tbl[RADIX],*p,*pn;
int slot,shift;
int i,j;
// Handle trivial cases
if(!list || !list->next) return(list);
// Initialize table
for(j=0; jnext;
slot = ((p->key) >> shift) & RADIX_MASK;
p->next = tbl[slot];
tbl[slot] = p;
p = pn;
}
// integrate back into partially ordered list
list = NULL;
for(j=0; jnext;
p->next = list;
list = p;
p = pn;
}
}
}
// fix prev pointers in list
list->prev = NULL;
p = list;
while(pn = p->next){
pn->prev = p;
p = pn;
}
return(list);
}
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: quicksort for linked list
Quicksort works just fine on a linked list, as long as you broaden
your view beyond the common array-based implementations. See
"http://www.cs.cmu.edu/~jbruce/sort.cc" for an example, although I
would recommend using a radix sort for linked lists in most situations
(sorry for the C++, but it was handy...).
9-Mar-2001 Re: quicksort for linked list by Helge [EMAIL PROTECTED]
Manoj Sontakke wrote:
Hi
Sorry, these questions do not belog here but i could not find any
better place.
1. Is quicksort on doubly linked list is implemented anywhere? I need it
for sk_buff queues.
I cannot see how the quicksort algorithm could work on a doubly
linked list, as it relies on being able to look
up elements directly as in an array.
You can probably find algorithms for sorting a linked list, but
it won't be quicksort.
It's quicksort as long as you do pivot/split, the array gymnastics
that most implementations do to avoid updating array elements isn't
really critical to its operation.
1. find out how many elements there are. (Count them if necessary)
2. Allocate a pointer array of this size.
3. fill the pointer array with pointers to list members.
4. quicksort the pointer array
5. Traverse the pointer array and set the links for each
list member to point to next/previous element pointed
to by the array. Now you have a sorted linked list!
I think a radix sort like the following would work better with about
the same (or less) storage, provided you're comparing ints (this is
for a kernel modification after all, right?). You just need to
determine the number of passes to cover all the bits in the numbers
you want to sort.
- Jim Bruce
#define RADIX_BITS 6
#define RADIX (1 RADIX_BITS)
#define RADIX_MASK (RADIX - 1)
struct item *radix_sort(struct item *list,int passes)
// Sort list, largest first
{
struct item *tbl[RADIX],*p,*pn;
int slot,shift;
int i,j;
// Handle trivial cases
if(!list || !list-next) return(list);
// Initialize table
for(j=0; jRADIX; j++) tbl[j] = NULL;
for(i=0; ipasses; i++){
// split list into buckets
shift = RADIX_BITS * i;
p = list;
while(p){
pn = p-next;
slot = ((p-key) shift) RADIX_MASK;
p-next = tbl[slot];
tbl[slot] = p;
p = pn;
}
// integrate back into partially ordered list
list = NULL;
for(j=0; jRADIX; j++){
p = tbl[j];
tbl[j] = NULL; // clear out table for next pass
while(p){
pn = p-next;
p-next = list;
list = p;
p = pn;
}
}
}
// fix prev pointers in list
list-prev = NULL;
p = list;
while(pn = p-next){
pn-prev = p;
p = pn;
}
return(list);
}
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
