Efficient IPC mechanism on Linux
Hi all.
At the web page
http://web.tiscali.it/lucavera/www/root/ecbm/index.htm
You can find the results of my attempt in modifing the linux kernel sources to implement a new Inter Process Communication mechanism.
It is called ECBM for Efficient Capability-Based Messaging.
In the reading You can also find the comparison of ECBM against some other commonly-used Linux IPC primitives (such as read/write on pipes or SYS V tools).
The results are quite clear.
Enjoy.
Luca Veraldi
----------------------------------------
Luca Veraldi
Graduate Student of Computer Science
at the University of Pisa
[email protected]
[email protected]
ICQ# 115368178
----------------------------------------
Quoted 11 lines · Luca Veraldi
Hi all.
At the web page
http://web.tiscali.it/lucavera/www/root/ecbm/index.htm
You can find the results of my attempt in modifing the linux kernel sources to implement a new Inter Process Communication mechanism.It is called ECBM for Efficient Capability-Based Messaging.
In the reading You can also find the comparison of ECBM against some other commonly-used Linux IPC primitives (such as read/write on pipes or SYS V tools).
The text is a little hard to follow for an English speaker. I can follow a fair bit and there are a few things I'd take issue with (forgive me if I'm misunderstanding your material)
1. Almost all IPC is < 512 bytes long. There are exceptions including X11 image passing which is an important performance one
2. One of the constraints that a message system has is that if it uses shared memory it must protect the memory queues from abuse. For example if previous/next pointers are kept in the shared memory one app may be able to trick another into modifying the wrong thing. Sometimes this matters.
3. An interesting question exists as to how whether you can create the same effect with current 2.6 kernel primitives. We have posix shared memory objects, we have read only mappings and we have extremely fast task switch and also locks (futex locks)
Also from the benching point of view it is always instructive to run a set of benchmarks that involve the sender writing all the data bytes, sending it and the receiver reading them all. Without this zero copy mechanisms (especially mmu based ones) look artificially good.
Quoted 3 lines
The text is a little hard to follow for an English speaker. I can follow a fair bit and there are a few things I'd take issue with (forgive me if I'm misunderstanding your material)
I know. I'm very sorry for this. I'm rewriting the text in English, so, don't bore with Italian. The new page will be up in a moment.
Quoted 2 lines
1. Almost all IPC is < 512 bytes long. There are exceptions including X11 image passing which is an important performance one
Sure for system needs. What about programming?
You can write application of any complexity.
Why do I have to be limited by kernel in sending 4056 bytes (for exmple, if I use SYS V message queues) instead of an arbitrary sized message?
Quoted 5 lines
2. One of the constraints that a message system has is that if it uses shared memory it must protect the memory queues from abuse. For example if previous/next pointers are kept in the shared memory one app may be able to trick another into modifying the wrong thing. Sometimes this matters.
Please, refer to address space.
If you don't have the piece of information you want to access into your own private address space, the only thing that will occur is a general protection fault and your process will be killed. Remember that, with my primitives, you're working with logical addresses that need relocation in hardware. The MMU contestually performs memory protection, too.
Quoted 4 lines
3. An interesting question exists as to how whether you can create the same effect with current 2.6 kernel primitives. We have posix shared memory objects, we have read only mappings and we have extremely fast task switch and also locks (futex locks)
I too need to use locks in my primitives. The fact that new kernel has faster locks also reduceses the completion time of my primitives.
Also. The central point is not to have10 instead of 50 assembler lines in the primitives. The central point is to implement communication primitives
that do not require physical copying of the messages being sent and received.
Lock probably reduces the time to write or read from a pipe. But the order of magnitute remains the same.
Task switching is relevant in all communication primitives.
Fast task switch means proportionally fast primitives. Also mine primitives.
Quoted 4 lines
Also from the benching point of view it is always instructive to run a set of benchmarks that involve the sender writing all the data bytes, sending it and the receiver reading them all. Without this zero copy mechanisms (especially mmu based ones) look artificially good.
The bench you are talking about is exactly the one I implemented to misure the IPC overhead.
We have 2 process communicating over a channel in a pipeline fashion. A writes some information in a buffer and sends it to B.
B receives and reads.
This for 1000 times.
Times reported are average time.
Bye,
Luca
Quoted 5 lines · Luca Veraldi
Also. The central point is not to have10 instead of 50 assembler lines in the primitives. The central point is to implement communication primitives
that do not require physical copying of the messages being sent and received.
The question (for smaller messages) is whether this is a win or not. While the data fits in L1 cache the copy is close to free compared with context switching and TLB overhead
Quoted 5 lines
We have 2 process communicating over a channel in a pipeline fashion. A writes some information in a buffer and sends it to B.
B receives and reads.
This for 1000 times.
Times reported are average time.
Ok - from you rexample I couldnt tell if B then touches each byte of data as well as having it appear in its address space.
Quoted 3 lines
The question (for smaller messages) is whether this is a win or not. While the data fits in L1 cache the copy is close to free compared with context switching and TLB overhead
I can answer for messages of 512 bytes (that I consider small). This is the smallest case considered in the work.
Completion times in this case are reported in graphs:
you have the time of write() on pipe,
of SYS V shmget() and of new primitives.
It's easy to compare numbers and to say if it is "a win or not".
Surely, transferring bytes from a cache line to another is at zero cost (that is, a single clock cycle of the cache unit).
But here, how can you matematically grant that,
using traditional IPC mechanism,
you'll find the info you want directly in cache?
This is quite far from being realistic.
In real world, what happens is that copying a page memory raises many cache faults... at least, more that copying a capability structure
(16 bytes long, as reported in the article).
Of course, if you want to send a single int, probably you don't have any reason to use capability. That's sure.
Quoted 2 lines
Ok - from you rexample I couldnt tell if B then touches each byte of data as well as having it appear in its address space.
It is irrilevant. The time reported in the work are the time needed to complete the IPC primitives.
After a send or a receive over the channel,
the two processes may do everything they want.
It is not interesting for us.
Bye,
Luca
Quoted 2 lines · Luca Veraldi
Surely, transferring bytes from a cache line to another is at zero cost (that is, a single clock cycle of the cache unit).
More complicated - when you move stuff you end up evicting another chunk from the cache, you can't armwave that out of existance because you yourself have created new eviction overhead for someone further down the line.
Quoted 3 lines
But here, how can you matematically grant that,
using traditional IPC mechanism,
you'll find the info you want directly in cache?
Because programs normally pass data they've touched to other apps. Your A/B example touches the data before sending even, but your example on receive does not which is very atypical.
Quoted 8 lines
Quoted 2 lines
Ok - from you rexample I couldnt tell if B then touches each byte of data as well as having it appear in its address space.
It is irrilevant. The time reported in the work are the time needed to complete the IPC primitives.
After a send or a receive over the channel,
the two processes may do everything they want.
It is not interesting for us.
Its vital to include it in the measurement of all three. Without it your measurements are meaningless. Look at it as an engineer. IPC involves writing to memory, making the data appear in the other task and then reading it. You also want to measure things like throughput of your IPC tasks running parallel to other processes doing stuff like pure memory bandwidth tests so you can measure the impact you have on the system although in this case thats probably less relevant by far
A message that is not in the archive (sent off-list or not yet received): [email protected]
A message that is not in the archive (sent off-list or not yet received): 001d01c37703$8edc10e0$36af7450@wssupremo
A message that is not in the archive (sent off-list or not yet received): [email protected]
Quoted 2 lines
I mean for benchmarks. You compared your implementation to a very old linux' one. There were big changes in these areas.
The overhead implied by a memcpy() is the same, in the oder of magnitude, ***whatever*** kernel version you can develop.
If you have to send, lt's say, 3 memory pages from A to B, using pipes you have to ***physically copy***
2 * 3 * PAGE_SIZE bytes
(firt time, sending; then receiving them. So two times). Which evals to 8192 * 3.
Using capability, the only thing you have to do is copying an amount of bytes that are linearly dependent by the number of pages: so, proportional to 3.
I you want the (quite) exact amount, it is
3 * sizeof(unsigned long) + sizeof(capability)
which evals to 12 + 16 = 28.
X is not present in the equation.
I compared pipes and SYS V IPC on Linux 2.2.4 with the new mechanism also developed over kernel 2.2.4!
The same inefficiency of the kernel support you are talking about affet all the primitives being examined in the article. Mine, too.
So the relative results will be quite the same.
Quoted 8 lines
you surely know, that it is just an implementation. The mechanisms have always been there, evolved from UNIX.
That is mainly the reason for them to exists: support the applications which use them.Will it be possible to base existing facilities on your approach? SVR5 messages (msg{get,snd,rcv}), for example?
(I have to ask, because I cannot understand the article, sorry)
Ah, ok. So let's continue to do ineffient things
only because it has always been so!
Compatibility is not a problem. Simply rewrite the write() and read() for pipes
in order to make them do the same thing done by zc_send() and zc_receive(). Or, if you are not referring to pipes, rewrite the support level of you anchient IPC primitives
in order to make them do the same thing done by zc_send() and zc_receive().
Bye,
Luca.
Quoted 2 lines · Luca Veraldi
The overhead implied by a
memcpy()is the same, in the oder of magnitude, ***whatever*** kernel version you can develop.
yes a copy of a page is about 3000 to 4000 cycles on an x86 box in the uncached case. A pagetable operation (like the cpu setting the accessed or dirty bit) is in that same order I suspect (maybe half this, but not a lot less). Changing pagetable content is even more because all the tlb's and internal cpu state will need to be flushed... which is also a microcode operation for the cpu. And it's deadly in an SMP environment.
Quoted 4 lines
yes a copy of a page is about 3000 to 4000 cycles on an x86 box in the uncached case. A pagetable operation (like the cpu setting the accessed or dirty bit) is in that same order I suspect (maybe half this, but not a lot less).
Probably you don't know what you're talking about. I don't know where you studied computer architectures, but... Let's answer.
To set the accessed or dirty bit you use
38 __asm__ __volatile__( LOCK_PREFIX
39 "btsl %1,%0" 40 :"=m" (ADDR) 41 :"Ir" (nr));
which is a ***SINGLE CLOCK CYCLE*** of cpu.
I don't think really that on any machine Firmware
a btsl will require 4000 cycles.
Neither on Intel x86.
Quoted 3 lines
Changing pagetable content is even more because all the tlb's and internal cpu state will need to be flushed... which is also a microcode operation for the cpu.
Good. The same overhead you will find accessing a message after a read form a pipe. There will occur many TLB faults. And the same apply copying the message to the pipe. Many many TLB faults.
Quoted 1 line
And it's deadly in an SMP environment.
You say "tlb's and internal cpu state will need to be flushed". The other cpus in an SMP environment can continue to work, indipendently. TLBs and cpu state registers are ***PER-CPU*** resorces.
Probably, it is worse the case of copying a memory page, because you have to hold some global lock all the time. This is deadly in an SMP environment,
because critical section lasts for thousand of cycles, instead of simply a few.
Quoted 11 lines · Luca Veraldi
To set the accessed or dirty bit you use
38
__asm____volatile__(LOCK_PREFIX39 "btsl %1,%0" 40 :"=m" (ADDR) 41 :"Ir" (nr));which is a ***SINGLE CLOCK CYCLE*** of cpu.
I don't think really that on any machine Firmware
a btsl will require 4000 cycles.
Neither on Intel x86.
For fun do the measurement on a pIV cpu. You'll be surprised.
The microcode "mark dirty" (which is NOT a btsl, it gets done when you do a write memory access to the page content) result will be in the 2000 to 4000 range I predict. There are things like SMP synchronisation to do, but also if the cpu marks a page dirty in the page table, that means the page table changes which means the pagetable needs to be marked in the
PMD. Which means the PMD changes, which means the PGD needs the PMD marked dirty. Etc Etc. It's microcode. It'll take several 1000 cycles.
Quoted 8 lines
Quoted 3 lines
Changing pagetable content is even more because all the tlb's and internal cpu state will need to be flushed... which is also a microcode operation for the cpu.
Good. The same overhead you will find accessing a message after a read form a pipe. There will occur many TLB faults. And the same apply copying the message to the pipe. Many many TLB faults.
A TLB fault in the normal case is about 7 cycles. But that's for a TLB not being present. For TLB that IS present being written to means going to microcode.
Quoted 6 lines
Quoted 2 lines
And it's deadly in an SMP environment.
You say "tlb's and internal cpu state will need to be flushed". The other cpus in an SMP environment can continue to work, indipendently. TLBs and cpu state registers are ***PER-CPU*** resorces.
if you change a page table, you need to flush the TLB on all other cpus that have that same page table mapped, like a thread app running on all cpu's at once with the same pagetables.
Quoted 2 lines
Probably, it is worse the case of copying a memory page, because you have to hold some global lock all the time.
why would you need a global lock for copying memory ?
Quoted 2 lines
For fun do the measurement on a pIV cpu. You'll be surprised. The microcode "mark dirty" (which is NOT a btsl, it gets done when you do
a write
Quoted 1 line
memory access to the page content) result will be in the 2000 to 4000
range I
Quoted 1 line
predict.
I'm not responsible for microarchitecture designer stupidity. If a simple STORE assembler instruction will eat up 4000 clock cycles, as you say here, well, I think all we Computer Scientists can go home and give it up now.
Quoted 5 lines
There are things like SMP synchronisation to do, but also
if the cpu marks a page dirty in the page table, that means the page table changes which means the pagetable needs to be marked in the PMD. Which means the PMD changes, which means the PGD needs the PMD marked dirty. Etc Etc. It's microcode. It'll take several 1000 cycles.
Please, return to the fact.
Modifying the page contents is done by that part of benchmark application we are not misuring.
That is, the code ***BEFORE*** the zc_send() (write() on pipe or whatever you choose)
and ***AFTER*** a zc_receive() (or read() from pipe ot whatever else). This is nice, thanks, but out of our interests.
We are only reading the relocation tables or inserting new entries in it. Not modifying page contents.
Quoted 3 lines
if you change a page table, you need to flush the TLB on all other cpus that have that same page table mapped, like a thread app running on all cpu's at once with the same pagetables.
Ok. Simply, this is not the case in my experiment. This does not apply.
We have no threads. But only detached process address spaces. Threads are a bit different from processes.
Quoted 1 line
why would you need a global lock for copying memory ?
System call sys_write() callslocks_verify_area() which callslocks_mandatory_area() which callslock_kernel()
oops...
global spin_lock locking...
SMP is crying...
But not so much, if the lock is not lasting much, is it right?
THIS IS NOT WHAT WE CALL A SHORT LOCK SECTION:
732 repeat:
733 /* Search the lock list for this inode for locks that conflict
with
734 * the proposed read/write.
735 */
736 for (fl = inode->i_flock; fl != NULL; fl = fl->fl_next) {
737 if (!(fl->fl_flags & FL_POSIX))
738 continue;
739 if (fl->fl_start > new_fl->fl_end)
740 break;
741 if (posix_locks_conflict(new_fl, fl)) {
742 error = -EAGAIN;
743 if (filp && (filp->f_flags & O_NONBLOCK))
744 break;
745 error = -EDEADLK;
746 if (posix_locks_deadlock(new_fl, fl))
747 break;
748
749 error = locks_block_on(fl, new_fl);
750 if (error != 0)
751 break;
752
753 /*
754 * If we've been sleeping someone might have 755 * changed the permissions behind our back. 756 */
757 if ((inode->i_mode & (S_ISGID | S_IXGRP)) !=S_ISGID)
758 break;
759 goto repeat;
760 }
761 }
Quoted 1 line
From the source code of your Operating System.
Quoted 11 lines · Luca Veraldi
Quoted 2 lines
For fun do the measurement on a pIV cpu. You'll be surprised. The microcode "mark dirty" (which is NOT a btsl, it gets done when you do
a write
Quoted 1 line
memory access to the page content) result will be in the 2000 to 4000
range I
Quoted 1 line
predict.
I'm not responsible for microarchitecture designer stupidity. If a simple STORE assembler instruction will eat up 4000 clock cycles, as you say here, well, I think all we Computer Scientists can go home and give it up now.
I'm saying it can. I don't want to go too deep into an arguement about microarchitectural details, but my point was that a memory copy of a page is NOT super expensive relative to several other effects that have to do with pagetable manipulations.
Quoted 8 lines
Quoted 3 lines
if you change a page table, you need to flush the TLB on all other cpus that have that same page table mapped, like a thread app running on all cpu's at once with the same pagetables.
Ok. Simply, this is not the case in my experiment. This does not apply.
We have no threads. But only detached process address spaces. Threads are a bit different from processes.
but the pipe code cannot know this so it has to do a cross cpu invalidate.
Quoted 6 lines
Quoted 1 line
why would you need a global lock for copying memory ?
System call
sys_write()callslocks_verify_area()which callslocks_mandatory_area()which callslock_kernel()
and... which is also releasing it before the copy
Quoted 4 lines
I'm saying it can. I don't want to go too deep into an arguement about microarchitectural details, but my point was that a memory copy of a page is NOT super expensive relative to several other effects that have to do with pagetable manipulations.
Sorry, but I cannot believe it.
Reading a page tagle entry and storing in into a struct capability is not comparable at all with the "for" needed to move bytes all around memory.
Quoted 1 line
but the pipe code cannot know this so it has to do a cross cpu invalidate.
Sorry for you. Don't knowning does not justify it. It's inefficient.
Quoted 1 line
and... which is also releasing it before the copy
Oh, yes. After wasting thousands of cycles, sure.
Bye,
Luca.
Quoted 4 lines · Luca Veraldi
Sorry, but I cannot believe it.
Reading a page tagle entry and storing in into a struct capability is not comparable at all with the "for" needed to move bytes all around memory.
Pardon my ignorance here, but the impression I get is that changing a page table entry is not as simple as just writing to a bit somewhere. I suppose it is if the page descriptor is not loaded into the TLB, but if it is, then you have to ensure that the TLB entry matches the page table; this may not be a quick operation.
I can think of a lot of other possible complications to this.
Quoted 7 lines
Pardon my ignorance here, but the impression I get is that changing a page table entry is not as simple as just writing to a bit somewhere. I suppose it is if the page descriptor is not loaded into the TLB, but if it is, then you have to ensure that the TLB entry matches the page table; this may not be a quick operation.
I can think of a lot of other possible complications to this.
I stopped writing about this question a lot of time ago. However, here we are.
If you modify the page tables as in my example (and then if you do so only for B's pagetable)
you can be sure the things you're modifying were not present in Firmware TLBs, not yet.
Because those pagetable entries refer to a logical address interval you've just allocated in B address space.
Bye,
Luca
Quoted 7 lines · Luca Veraldi
If you modify the page tables as in my example (and then if you do so only for B's pagetable)
you can be sure the things you're modifying were not present in Firmware TLBs, not yet.Because those pagetable entries refer to a logical address interval you've just allocated in B address space.
They may be present in some form, but you are right the task switch will flush them in the non SMP case on the x86 platform. In the SMP case it wont work.
Alan
Quoted 4 lines · Luca Veraldi
SMP is crying...
But not so much, if the lock is not lasting much, is it right?THIS IS NOT WHAT WE CALL A SHORT LOCK SECTION:
This is the difference between science and engineering. Its a path that isnt normally taken and normally if taken takes almost no loops.
Quoted 11 lines · Luca Veraldi
Quoted 2 lines
For fun do the measurement on a pIV cpu. You'll be surprised. The microcode "mark dirty" (which is NOT a btsl, it gets done when you do
a write
Quoted 1 line
memory access to the page content) result will be in the 2000 to 4000
range I
Quoted 1 line
predict.
I'm not responsible for microarchitecture designer stupidity. If a simple STORE assembler instruction will eat up 4000 clock cycles, as you say here, well, I think all we Computer Scientists can go home and give it up now.
Unfortunately you are responsible for working with the constructs reality has given you. Giving up is childish. Where there is a lose, there's a chance it was a tradeoff for a win elsewhere.
Quoted 3 lines · Luca Veraldi
I'm not responsible for microarchitecture designer stupidity. If a simple STORE assembler instruction will eat up 4000 clock cycles, as you say here, well,
If current trends continue, a L2 cache miss will be taking 5000 cycles in 15 to 20 years.
Quoted 1 line
I think all we Computer Scientists can go home and give it up now.
While I have seen some evidence of computer scientists going home and ignoring the problems presented to them by current hardware constraints, I'd really prefer it if they took up the challenge and did the research on how we should deal with hardware in the future.
In fact, I've made up a little (incomplete) list of things that I suspect are in need of serious CS research, because otherwise both OS theory and practice will be unable to deal with the hardware of the next decade.
http://surriel.com/research_wanted/
If you have any suggestions for the list, please let me know.
Signature · 3 lines
"Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it." - Brian W. Kernighan
Re: Rik's list of CS challenges
I got one:
I've been paying attention the MRAM
http://www.research.ibm.com/resources/news/20030610_mram.shtml (and the other NV rams comming up, most notabily the optical/polymer
http://www.pcw.co.uk/news/1143633 techs).
What interest me is that with multiple candidates in the pipeline, it's a high probability that we'll have a non-volatile DRAM replacement hitting mainstream computer market within 5-10 years.
You have the obvious PDA/Laptop application, which I'll not dwell on.
You have the HA server application where you want fast reboot on power failure etc.
I'd expect that there will be a demand of never reboot, only seemless continue. Booting is after all a "hack" to get around
- OS bugs
- an easy way of detecting new HW and config the OS according to HW.
- An easy way to upgrade the kernel
hotplug demands are already rendering pt 2 obsolete. UPgrading the kernel while running would be a cool feature. One of the promises of the micro kernel archs in the early 90's
Is it possible to "reboot" the kernel without affecting the running apps on the machine?
What become more interesting is that while you may have NV RAM, it's not likely that MRAM is viable on the processor chip. The manufacture process may be too expensive, or outright impossible, (polymers on chips that hold 80 degrees C in not likely), leaving you with volatile register and cache but NV Main RAM.
- should the OS now schedule "paging" between cache and RAM?
- atomic syncing/updates of regs/cache to RAM? (checkpointing)
A merge of FS and RAM? (didn't the AS/400 have mmap'ed disks?)
And all the applications I haven't even thought of.
TJ
Quoted 26 lines · Rik van Riel
Quoted 3 lines · Luca Veraldi
I'm not responsible for microarchitecture designer stupidity. If a simple STORE assembler instruction will eat up 4000 clock cycles, as you say here, well,
If current trends continue, a L2 cache miss will be taking 5000 cycles in 15 to 20 years.
Quoted 1 line
I think all we Computer Scientists can go home and give it up now.
While I have seen some evidence of computer scientists going home and ignoring the problems presented to them by current hardware constraints, I'd really prefer it if they took up the challenge and did the research on how we should deal with hardware in the future.
In fact, I've made up a little (incomplete) list of things that I suspect are in need of serious CS research, because otherwise both OS theory and practice will be unable to deal with the hardware of the next decade.
http://surriel.com/research_wanted/
If you have any suggestions for the list, please let me know.
Signature · 9 lines
Terje Eggestad Senior Software Engineer dir. +47 22 62 89 61 mob. +47 975 31 57 fax. +47 22 62 89 51 [email protected] Scali - www.scali.com High Performance Clustering
Re: Rik's list of CS challenges
Quoted 5 lines · Terje Eggestad
What become more interesting is that while you may have NV RAM, it's not likely that MRAM is viable on the processor chip. The manufacture process may be too expensive, or outright impossible, (polymers on chips that hold 80 degrees C in not likely), leaving you with volatile register and cache but NV Main RAM.
We effectively handle that case now with the suspend-to-ram feature.
Quoted 1 line
A merge of FS and RAM? (didn't the AS/400 have mmap'ed disks?)
Persistant storage systems. These tend to look very unlike Linux because they throw out the idea of a file system as such. The issues with debugging if they break and backups make my head hurt but other folk seem to think they are solved problems
Re: Rik's list of CS challenges
Quoted 12 lines · Alan Cox
Quoted 5 lines · Terje Eggestad
What become more interesting is that while you may have NV RAM, it's not likely that MRAM is viable on the processor chip. The manufacture process may be too expensive, or outright impossible, (polymers on chips that hold 80 degrees C in not likely), leaving you with volatile register and cache but NV Main RAM.
We effectively handle that case now with the suspend-to-ram feature.
Quoted 7 lines
Quoted 1 line
A merge of FS and RAM? (didn't the AS/400 have mmap'ed disks?)
Persistant storage systems. These tend to look very unlike Linux because they throw out the idea of a file system as such. The issues with debugging if they break and backups make my head hurt but other folk seem to think they are solved problems
I see no reason to get rid of file systems - they provide a nice and established way of organizing data. Persistent RAM offer other advantages though - no need for disk caching, mmap simply gives access to the memory, execute without loading first.
Helge Hafting
Quoted 8 lines · Luca Veraldi
To set the accessed or dirty bit you use
38
__asm____volatile__(LOCK_PREFIX39 "btsl %1,%0" 40 :"=m" (ADDR) 41 :"Ir" (nr));which is a ***SINGLE CLOCK CYCLE*** of cpu.
Its a _lot_ more than that in the normal case. Upwards of 60 clocks on a PIV. You then need to reload cr3 if you touched permissions which means every cached TLB in the system is lost, and you may need to do a cross CPU IPI on SMP (which takes a long time)
Quoted 3 lines
You say "tlb's and internal cpu state will need to be flushed". The other cpus in an SMP environment can continue to work, indipendently. TLBs and cpu state registers are ***PER-CPU*** resorces.
Think of a threaded app passing a message to another app. You have to do the cross CPU flush in order to prevent races where another thread can scribble on data it doesnt own. Assuming a reasonable TLB reuse rate thats 120 plus TLB reloads. The newer CPU's cache TLB's in L1/L2 so thats not too bad but it all adds up. On SMP its a real pain
Quoted 3 lines
Probably, it is worse the case of copying a memory page, because you have to hold some global lock all the time. This is deadly in an SMP environment,
You don't need a global lock to copy memory.
One thing I do agree with you on is the API aspect - and that is problematic. The current API leaves data also owned by the source. If I write "fred" down a pipe I still own the "fred" bits. The method you propose was added long ago go to Solaris (see "doors") and its not exactly the most used interface even there.
Quoted 5 lines
Quoted 3 lines
Probably, it is worse the case of copying a memory page, because you have to hold some global lock all the time. This is deadly in an SMP environment,
You don't need a global lock to copy memory.
See sources. You neek to lock_kernel() for a great amount of instructions like any nother kernel function.
There are kernel locks all around in sources. So don't come here and talk about locking ineffiency. Because scarse scalability of Linux on multiprocessor is a reality nobody can hide.
With or without my primitives.
Quoted 3 lines
One thing I do agree with you on is the API aspect - and that is problematic. The current API leaves data also owned by the source. If I write "fred" down a pipe I still own the "fred" bits.
Even with my API. Data doesn't disapper magically
from the sender logical address space.
Also, with minor changes, you can use my primitives
to implement a one-copy channel, if shared memory among processes sounds to you as a blasfemy.
Always better than two-fase-copying current pipe implementation.
Quoted 3 lines
The
method you propose was added long ago go to Solaris (see "doors") and its not exactly the most used interface even there.
Sincerely, I COMPLETELY DON'T CARE.
If it is used or not, it's completely irrilevant, when valueing performance.
Good bye.
Luca
Quoted 4 lines · Luca Veraldi
There are kernel locks all around in sources. So don't come here and talk about locking ineffiency. Because scarse scalability of Linux on multiprocessor is a reality nobody can hide.
Well if you will read the 2.2 code sure. If you want to argue scalability I suggest you look at current code and the SGI Altix boxes
Quoted 9 lines · Arjan van de Ven
Quoted 2 lines
The overhead implied by a
memcpy()is the same, in the oder of magnitude, ***whatever*** kernel version you can develop.yes a copy of a page is about 3000 to 4000 cycles on an x86 box in the uncached case. A pagetable operation (like the cpu setting the accessed or dirty bit) is in that same order I suspect (maybe half this, but not a lot less). Changing pagetable content is even more because all the tlb's and internal cpu state will need to be flushed... which is also a microcode operation for the cpu. And it's deadly in an SMP environment.
I have just done a measurement on a 366MHz PII Celeron. The test is quite crude, but these numbers are upper bounds on the timings:
mean 813 cycles to:
page fault
install zero page
remove zero page
(= read every page from MAP_ANON region and unmap, repeatedly)
mean 11561 cycles to:
page fault
copy zero page
install copy
remove copy
(= write every page from MAP_ANON region and unmap, repeatedly)
I think that makes a clear case for avoiding page copies.
-- Jamie
Quoted 10 lines
mean 11561 cycles to:
page fault
copy zero page
install copy
remove copy(= write every page from
MAP_ANONregion and unmap, repeatedly)I think that makes a clear case for avoiding page copies.
Thanks.
Quoted 4 lines · Jamie Lokier
Quoted 3 lines · Arjan van de Ven
Quoted 2 lines
The overhead implied by a
memcpy()is the same, in the oder of magnitude, ***whatever*** kernel version you can develop.
Quoted 8 lines
Quoted 6 lines
yes a copy of a page is about 3000 to 4000 cycles on an x86 box in the uncached case. A pagetable operation (like the cpu setting the accessed or dirty bit) is in that same order I suspect (maybe half this, but not a lot less). Changing pagetable content is even more because all the tlb's and internal cpu state will need to be flushed... which is also a microcode operation for the cpu. And it's deadly in an SMP environment.
I have just done a measurement on a 366MHz PII Celeron
This test is sort of the worst case against my argument:
1) It's a cpu with low memory bandwidth
2) It's a 1 CPU system
3) It's a pII not pIV; the pII is way more efficient cycle wise for pagetable operations
Quoted 5 lines
This test is sort of the worst case against my argument:
1) It's a cpu with low memory bandwidth
2) It's a 1 CPU system
3) It's a pII not pIV; the pII is way more efficient cycle wise for pagetable operations
I'm a Compuer Science graduate. And at least one single thing I've learned in my studies.
More efficient Firmware support
(such as an extremely wide memory bandwith
or tens of CPUs in an SMP/NUMA
or efficient cache line transfer support)
DOES NOT ALLOW YOU TO WASTE CYCLES IN DOING USELESS THINGS,
such as TWO physical copies of a message if a process want to cooperate with another one.
We are not engineer that simply have to let the things work.
That's all.
Luca.
Quoted 7 lines · Arjan van de Ven
Quoted 1 line
I have just done a measurement on a 366MHz PII Celeron
This test is sort of the worst case against my argument:
1) It's a cpu with low memory bandwidth
2) It's a 1 CPU system
3) It's a pII not pIV; the pII is way more efficient cycle wise for pagetable operations
I thought that later generation CPUs were supposed to have lower memory bandwidth relative to the CPU core, so CPU operations are better than copying. Hence all the fancy special memory instructions, to work around that.
Not that it matters. I think the 366 Celeron is typical of a lot of computers being used today. I still use it every day, after all.
-- Jaie
Quoted 2 lines · Jamie Lokier
I thought that later generation CPUs were supposed to have lower memory bandwidth relative to the CPU core
this is far more true for "random/access" latency than for streaming bandwidth. Memory is sort of starting to be like disk IO in this regard.
Quoted 1 line
Memory is sort of starting to be like disk IO in this regard.
Good. So the less you copy memory all around, the better you permorm.
Quoted 3 lines · Luca Veraldi
Quoted 1 line
Memory is sort of starting to be like disk IO in this regard.
Good. So the less you copy memory all around, the better you permorm.
Actually it's "the less discontiguos memory you touch the better you perform". Just like a 128Kb read is about the same cost as a 4Kb disk read, the same is starting to become true for memory copies. So in the extreme the memory copy is one operation only.
Quoted 5 lines · Luca Veraldi
Quoted 2 lines
Memory is sort of starting to be like disk IO in this regard.
Good. So the less you copy memory all around, the better you permorm.
Hi Luca,
There was a zero-copy pipe implementation floating around a while ago I think. Did you have a look at that? IIRC it had advantages and disadvantages over regular pipes in performance.
Nick
Quoted 4 lines
Hi Luca,
There was a zero-copy pipe implementation floating around a while ago I think. Did you have a look at that? IIRC it had advantages and disadvantages over regular pipes in performance.
Sorry, but i subscripted this mailing-list only one day ago. Advantages and disadvantages depends on what actually you implement and on how you do that.
I can only say that capabilities are a disadvantage only with very very short messages
(that is, a few bytes). And this disadvantage is theoretically demonstrable.
But, let's say also that such elementary messages are meaningful only in the kernel
and for kernel purposes.
User processes are another tail.
Bye,
Luca
Quoted 10 lines · Luca Veraldi
Quoted 5 lines
Hi Luca,
There was a zero-copy pipe implementation floating around a while ago I think. Did you have a look at that? IIRC it had advantages and disadvantages over regular pipes in performance.Sorry, but i subscripted this mailing-list only one day ago. Advantages and disadvantages depends on what actually you implement and on how you do that.
Yes you're right. Just search for it. It would be interesting to compare them with your implementation.
Quoted 11 lines
I can only say that capabilities are a disadvantage only with very very short messages
(that is, a few bytes). And this disadvantage is theoretically demonstrable.But, let's say also that such elementary messages are meaningful only in the kernel
and for kernel purposes.User processes are another tail.
I'm not too sure, I was just pointing you to zero copy pipes because they did have some disadvantages which is why they weren't included in the kernel. Quite possibly your mechanism doesn't suffer from these.
What would really help convince everyone is, of course, "real world" benchmarks. I like your ideas though ;)
Quoted 5 lines
Yes you're right. Just search for it. It would be interesting to compare them with your implementation.
I'm not too sure, I was just pointing you to zero copy pipes because they did have some disadvantages which is why they weren't included in the kernel. Quite possibly your mechanism doesn't suffer from these.
Ok. I'll search for them.
Quoted 2 lines
What would really help convince everyone is, of course, "real world" benchmarks. I like your ideas though ;)
Thanks.
Luca
Quoted 3 lines · Nick Piggin
There was a zero-copy pipe implementation floating around a while ago I think. Did you have a look at that? IIRC it had advantages and disadvantages over regular pipes in performance.
FreeBSD had one, it was lightning fast until you used the data the other end of the pipe. Im not sure what happened to it in the long term.
Hi!
Quoted 23 lines
Quoted 9 lines
Quoted 2 lines
The overhead implied by a
memcpy()is the same, in the oder of magnitude, ***whatever*** kernel version you can develop.yes a copy of a page is about 3000 to 4000 cycles on an x86 box in the uncached case. A pagetable operation (like the cpu setting the accessed or dirty bit) is in that same order I suspect (maybe half this, but not a lot less). Changing pagetable content is even more because all the tlb's and internal cpu state will need to be flushed... which is also a microcode operation for the cpu. And it's deadly in an SMP environment.
I have just done a measurement on a 366MHz PII Celeron. The test is quite crude, but these numbers are upper bounds on the timings:
mean 813 cycles to:
page fault
install zero page
remove zero page(= read every page from
MAP_ANONregion and unmap, repeatedly)mean 11561 cycles to:
Quoted 8 lines
page fault
copy zero page
install copy
remove copy(= write every page from
MAP_ANONregion and unmap, repeatedly)I think that makes a clear case for avoiding page copies.
Can you make it available so we can test on, say, 900MHz athlon? Or you can have it tested on 1800MHz athlon64, that's about as high end as it can get.
Pavel
Signature · 2 lines
When do you have a heart between your knees? [Johanka's followup: and *two* hearts?]
Quoted 3 lines · Pavel Machek
Can you make it available so we can test on, say, 900MHz athlon? Or you can have it tested on 1800MHz athlon64, that's about as high end as it can get.
I just deleted the program, so here's a rewrite :)
#include <sys/mman.h>
int main()
{
int i, j;
for (j = 0; j < 64; j++) {
volatile char * ptr =
mmap (0, 4096 * 4096, PROT_READ | PROT_WRITE,
MAP_PRIVATE | MAP_ANON, -1, 0);
for (i = 0; i < 4096; i++) {
#if 1
*(ptr + 4096 * i) = 0; /* Write */
#else
(void) *(ptr + 4096 * i); /* Read */
#endif
}
munmap ((void *) ptr, 4096 * 4096);
}
return 0;
}Smallest results, from "gcc -o test test.c -O2; time ./test" on a 1500MHz dual Athlon 1800 MP:
Write:
real 0m1.316s user 0m0.059s sys 0m1.256s ==> 7531 cycles per page
Read:
real 0m0.199s user 0m0.053s sys 0m0.146s ==> 1139 cycles per page
As I said, it's a crude upper bound.
-- Jamie
Hi!
Quoted 37 lines
Quoted 3 lines
Can you make it available so we can test on, say, 900MHz athlon? Or you can have it tested on 1800MHz athlon64, that's about as high end as it can get.
I just deleted the program, so here's a rewrite :)
#include <sys/mman.h> int main() { int i, j; for (j = 0; j < 64; j++) { volatile char * ptr = mmap (0, 4096 * 4096, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANON, -1, 0); for (i = 0; i < 4096; i++) { #if 1 *(ptr + 4096 * i) = 0; /* Write */ #else (void) *(ptr + 4096 * i); /* Read */ #endif } munmap ((void *) ptr, 4096 * 4096); } return 0; }Smallest results, from "gcc -o test
test.c-O2; time ./test" on a 1500MHz dual Athlon 1800 MP:Write:
real 0m1.316s user 0m0.059s sys 0m1.256s ==> 7531 cycles per page
Quoted 8 lines
Read:
real 0m0.199s user 0m0.053s sys 0m0.146s ==> 1139 cycles per pageAs I said, it's a crude upper bound.
But you should also time memory remapping stuff on same cpu, no?
Pavel
Signature · 2 lines
When do you have a heart between your knees? [Johanka's followup: and *two* hearts?]
Quoted 1 line · Pavel Machek
But you should also time memory remapping stuff on same cpu, no?
Yes, but can I be bothered ;)
Like I said, it's a crude upper bound.
We know the remapping time will be about the same in both tests, because all it does is the same vma operations and the same TLB invalidations.
-- Jamie
Luca Veraldi, Wed, Sep 10, 2003 11:18:48 +0200:
Quoted 5 lines
Quoted 2 lines
Will it be possible to base existing facilities on your approach? SVR5 messages (msg{get,snd,rcv}), for example?
Ah, ok. So let's continue to do ineffient things
only because it has always been so!
It is because the interface is perfectly enough. You still can implement zero-copy local transfers for pipes for read and write calls.
And for small amounts, where it is impossible to do zero-copy does not bring noticable advantages (as was already mentioned by Alan).
Quoted 5 lines
Compatibility is not a problem. Simply rewrite the
write()andread()for pipes in order to make them do the same thing done byzc_send()andzc_receive(). Or, if you are not referring to pipes, rewrite the support level of you anchient IPC primitives in order to make them do the same thing done byzc_send()andzc_receive().
If it is possible, why new user-side interface?
-alex
Quoted 8 lines
Quoted 6 lines
Compatibility is not a problem. Simply rewrite the
write()andread()for pipes in order to make them do the same thing done byzc_send()andzc_receive(). Or, if you are not referring to pipes, rewrite the support level of you anchient IPC primitives in order to make them do the same thing done byzc_send()andzc_receive().If it is possible, why new user-side interface?
Because my programming model is clear and easy.
Linux one's is far from being so, in my opinion.
Bye,
Luca
Luca Veraldi, Wed, Sep 10, 2003 14:14:00 +0200:
Quoted 9 lines
Quoted 7 lines
Quoted 5 lines
Compatibility is not a problem. Simply rewrite the
write()andread()for pipes in order to make them do the same thing done byzc_send()andzc_receive(). Or, if you are not referring to pipes, rewrite the support level of you anchient IPC primitives in order to make them do the same thing done byzc_send()andzc_receive().If it is possible, why new user-side interface?
Because my programming model is clear and easy.
does anyone, besides you, says so?
Quoted 1 line
Linux one's is far from being so, in my opinion.
it is widely accepted one.
Quoted 1 line
it is widely accepted one.
Widely accepted does not necessary implies clear.
Sorry if I consider more readable this:
ch=acquire(CHANNEL_ID);
instead of this:while((fd = open("fifo", O_WRONLY)) < 0) ;
But this is quite an aestethical fact.
If you like "open" and "write", open Emacs and do a global replace "acquire" with "open"
and
"zc_send" with "write".
Few other minor details will make it a compatible interface.
------------------------------
Fashion is a variable
but style is a constant
------------------------------ Larry Wall
Bye,
Luca
Luca Veraldi, Wed, Sep 10, 2003 14:29:37 +0200:
Quoted 4 lines
Quoted 1 line
it is widely accepted one.
Widely accepted does not necessary implies clear.
but it does imply "tested". And widely used. And well-known.
Quoted 1 line
but it does imply "tested". And widely used. And well-known.
And inefficient, too.
Sorry, but I use theory not popular convention to judge.
Bye,
Luca
Luca Veraldi, Wed, Sep 10, 2003 14:36:19 +0200:
Quoted 3 lines
Quoted 1 line
but it does imply "tested". And widely used. And well-known.
And inefficient, too.
yes, probably. Until proven. What exactly wrong with api?
Quoted 1 line
Sorry, but I use theory not popular convention to judge.
I personally do not see deficiencies of the mentioned apis.
Quoted 4 lines · Luca Veraldi
Quoted 1 line
but it does imply "tested". And widely used. And well-known.
And inefficient, too.
Sorry, but I use theory not popular convention to judge.
But theory is often far from practice ...
Theory is something which uses some abstraction to "model" reality. Which often means oversimplification of the problem or simply the fact that a real case has got much more (probably hidden) parameters affecting the problem. Maybe these parameters are very hard to even detect at the FIRST sight. That's why most software development starting from theory _BUT_ some "REAL WORLD" benchmark/test should confirm the truth of that theory. Or even think about relativity theory by Einstein: the theory is good, but it's even better to prove it in the real life too: perturbation in the orbit of Mercury, or affect to the visible position of stars at an eclipse. That was the point when Einstein's theory bacome to be widely used by science.
So I thing it's no use to start a flame thread here. Implement that IPC solution, and test it. If it becomes a good one, everybody will be happy with your work. If not, at least you've tried, and maybe you will also learn from it. Since Linux is open source, you have nothing to lose with your implementation.
- Gábor (larta'H)
Quoted 5 lines
So I thing it's no use to start a flame thread here. Implement that IPC solution, and test it. If it becomes a good one, everybody will be happy with your work. If not, at least you've tried, and maybe you will also learn from it. Since Linux is open source, you have nothing to lose with your implementation.
It is exactly what I've done. But, did you read the page? I've implemented the IPC mechanism... And tested, too.
The numbers reported in tables weren't the fuit of my immagination, dear.
Bye,
Luca
hrm, you may find things related to the Password-Capability system and the Walnut kernel of interest - these systems take this kind of IPC to the extreme :) (ahhh... research OS hw & sw - except you *do not* want to see the walnut source - it makes ppl want to crawl up and cry).
http://www.csse.monash.edu.au/~rdp/fetch/castro-thesis.ps
and check the Readme.txt at
http://www.csse.monash.edu.au/courseware/cse4333/rdp-ma terial/ for stuff on Multi and password-capabilities.
interesting stuff, the Castro thesis does do some comparisons to FreeBSD (1.1 amazingly enough) - although the number of real world applications on these systems is minimal (and in the current state impossible - nobody can remember how to get userspace going on Walnut, we may have broken it) and so real-world comparisons just don't really happen these days. Maybe after a rewrite (removing some brain-damage of the original design).
This is all related to my honors work,
http://www.flamingspork.com/honors/
although my site needs an update.
I'm working on the design and simulation of an improved storage system.
Quoted 33 lines · Luca Veraldi
Hi all.
At the web page
http://web.tiscali.it/lucavera/www/root/ecbm/index.htm
You can find the results of my attempt in modifing the linux kernel sources to implement a new Inter Process Communication mechanism.It is called ECBM for Efficient Capability-Based Messaging.
In the reading You can also find the comparison of ECBM against some other commonly-used Linux IPC primitives (such as read/write on pipes or SYS V tools).
The results are quite clear.
Enjoy.
Luca Veraldi----------------------------------------
Luca VeraldiGraduate Student of Computer Science
at the University of Pisa[email protected]
[email protected]
ICQ# 115368178
----------------------------------------
-
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/
Quoted 11 lines
hrm, you may find things related to the Password-Capability system and the Walnut kernel of interest - these systems take this kind of IPC to the extreme :) (ahhh... research OS hw & sw - except you *do not* want to see the walnut source - it makes ppl want to crawl up and cry).
http://www.csse.monash.edu.au/~rdp/fetch/castro-thesis.ps
and check the Readme.txt at
http://www.csse.monash.edu.au/courseware/cse4333/rdp-ma terial/ for stuff on Multi and password-capabilities.
Quoted 7 lines
interesting stuff, the Castro thesis does do some comparisons to FreeBSD (1.1 amazingly enough) - although the number of real world applications on these systems is minimal (and in the current state impossible - nobody can remember how to get userspace going on Walnut, we may have broken it) and so real-world comparisons just don't really happen these days. Maybe after a rewrite (removing some brain-damage of the original design).
Thanks. It's really very interesting...
Bye,
Luca
Ciao Luca,
Quoted 6 lines · Luca Veraldi
Hi all.
At the web page
http://web.tiscali.it/lucavera/www/root/ecbm/index.htm
You can find the results of my attempt in modifing the linux kernel sources to implement a new Inter Process Communication mechanism.
Quoted 7 lines
It is called ECBM for Efficient Capability-Based Messaging.
In the reading You can also find the comparison of ECBM against some other commonly-used Linux IPC primitives (such as read/write on pipes or SYS V tools).
The results are quite clear.
in terms of design as far as I can tell the most efficient way to do message passing is not pass the data through the kernel at all (no matter if you intend to copy it or not), and to simply use futex on top of shm to synchronize/wakeup the access. If we want to make an API widespread, that should be simply an userspace library only.
It's very inefficient to mangle pagetables and flush the tlb in a flood like you're doing (or better like you should do), when you can keep the memory mapped in *both* tasks at the same time *always* and there's no need of any kernel modification at all for that much more efficient design that I'm suggesting. Obviously lots of apps are already using this design and there's no userspace API simply because that's not needed. The only thing we need from the kernel is the wakeup mechanism and that's already provided by the futex (in the past userspae apps using this design used sched_yield, and that was very bad).
About the implementation - the locking looks very wrong: you miss the page_table_lock in all the pte walking, you take a totally worthless lock_kernel() all over the place for no good reason, and the unconditional set_bit(PG_locked) clear_bit(PG_locked) on random pieces of ram almost guarantees that you'll corrupt ram quickly (the PG_locked is reserved for I/O serialization, the same ram that you're working on can be sent to disk or to swap by the kernel at the same time and it can be already locked, you can't clear_bit unless you're sure you're the guy that owns the lock, and you aren't sure because you didn't test if you're the owner, so that smeels like an huge bug that will random corrupt ram, like the pte walking race).
there's also an obvious DoS that is trivial to generate by locking in ram some 64G of ram with ecbm_create_capability() see the for(count=0; count<pages; ++count) atomic_inc (btw, you should use get_page, and all the operations like LockPage to play with pages).
I also don't see where you flush the tlb after the set_pte, and where you release the ram pointed by the pte (it seems you're leaking plenty of memory that way).
I didn't check at all the credential checks (I didn't run into it while reading the code, but I assume I overlooked it). (do you rely on a random number? that's probably statistically secure, but we can guarantee security on a local box, we must not work by luck whenever possible)
this was a very quick review, hope this helps,
Andrea
/*
* If you refuse to depend on closed software for a critical
* part of your business, these links may be useful:
*
* rsync.kernel.org::pub/scm/linux/kernel/bkcvs/linux-2.5/
* rsync.kernel.org::pub/scm/linux/kernel/bkcvs/linux-2.4/
* http://www.cobite.com/cvsps/
*
* svn://svn.kernel.org/linux-2.6/trunk
* svn://svn.kernel.org/linux-2.4/trunk
*/
Quoted 3 lines · Andrea Arcangeli
About the implementation - the locking looks very wrong: you miss the
page_table_lockin all the pte walking, you take a totally worthlesslock_kernel()all over the place for no good reason, and the
sorry for the self followup, but I just read another message where you mention 2.2, if that was for 2.2 the locking was the ok.
all other problems remains though.
Andrea
/*
* If you refuse to depend on closed software for a critical
* part of your business, these links may be useful:
*
* rsync.kernel.org::pub/scm/linux/kernel/bkcvs/linux-2.5/
* rsync.kernel.org::pub/scm/linux/kernel/bkcvs/linux-2.4/
* http://www.cobite.com/cvsps/
*
* svn://svn.kernel.org/linux-2.6/trunk
* svn://svn.kernel.org/linux-2.4/trunk
*/
Quoted 2 lines
sorry for the self followup, but I just read another message where you mention 2.2, if that was for 2.2 the locking was the ok.
Oh, good. I was already going to put my head under sand. :-)
I'm not so expert about the kernel. I've just read [ORLL] and some bits of the kernel sources.
So, error in the codes are not so strange.
But, it's better now that you know we are talking about version 2.2...
I'm glad to hear that locking are ok.
You say:
Quoted 8 lines
in terms of design as far as I can tell the most efficient way to do message passing is not pass the data through the kernel at all (no matter if you intend to copy it or not), and to simply use futex on top of shm to synchronize/wakeup the access. If we want to make an API widespread, that should be simply an userspace library only.
It's very inefficient to mangle pagetables and flush the tlb in a flood like you're doing (or better like you should do), when you can keep the
I guess futex are some kind of semaphore flavour under linux 2.4/2.6. However, you need to use SYS V shared memory in any case. Tests for SYS V shared memory are included in the web page (even though using SYS V semaphores).
I don't think, reading the numbers, that managing pagetables "is very inefficient".
I think very inefficient are SYS V semaphore orethe double-copying channel you call a pipe.
Quoted 4 lines
there's also an obvious DoS that is trivial to generate by locking in ram some 64G of ram with
ecbm_create_capability()see the for(count=0; count<pages; ++count)atomic_inc(btw, you should useget_page, and all the operations like LockPage to play with pages).
As I say in the web page,
having all the pages locked in memory is not a necessary condition
for the applicability of communication mechanisms based on capabilities. Simply, it make it easier to write the code and does not make me crazy with the Linux swapping system.
Bye bye,
Luca
Quoted 4 lines · Luca Veraldi
Quoted 2 lines
sorry for the self followup, but I just read another message where you mention 2.2, if that was for 2.2 the locking was the ok.
Oh, good. I was already going to put my head under sand. :-)
;)
Quoted 4 lines
I'm not so expert about the kernel. I've just read [ORLL] and some bits of the kernel sources.
So, error in the codes are not so strange.
Ok no problem then.
Quoted 12 lines
But, it's better now that you know we are talking about version 2.2...
I'm glad to hear that locking are ok.
You say:
Quoted 6 lines
in terms of design as far as I can tell the most efficient way to do message passing is not pass the data through the kernel at all (no matter if you intend to copy it or not), and to simply use futex on top of shm to synchronize/wakeup the access. If we want to make an API widespread, that should be simply an userspace library only.
Quoted 5 lines
Quoted 2 lines
It's very inefficient to mangle pagetables and flush the tlb in a flood like you're doing (or better like you should do), when you can keep the
I guess futex are some kind of semaphore flavour under linux 2.4/2.6. However, you need to use SYS V shared memory in any case.
I need shared memory yes, but I can generate it with /dev/shm or clone(), it doesn't really make any difference. I would never use the ugly SYSV IPC API personally ;).
Quoted 2 lines
Tests for SYS V shared memory are included in the web page (even though using SYS V semaphores).
IPC semaphores are a totally different thing.
Basically the whole ipc/ directory is an inefficient obsolete piece of code that nobody should use.
The real thing is (/dev/shm || clone()) + futex.
Quoted 2 lines
I don't think, reading the numbers, that managing pagetables "is very inefficient".
Yep, it can be certainly more efficient than IPC semaphores or whatever IPC thing in ipc.
However the speed of the _shm_ API doesn't matter, you map the shm only once and you serialize the messaging with the futex. So even if it takes a bit longer to setup the shm with IPC shm, it won't matter, even using IPC shm + futex would be fine (despite I find /dev/shm much more friendy as an API).
Quoted 2 lines
I think very inefficient are SYS V semaphore orethe double-copying channel you call a pipe.
you're right in term of bandwidth if the only thing the reader and the writer do is to make the data transfer.
However if the app is computing stuff besides listening to the pipe (for example if it's in noblocking) the double copying allows the writer, to return way before the reader started reading the info. So the intermediate ram increases a bit the parallelism. One could play tricks with cows as well though but it would be way more complex than the current double copy ;).
(as somebody pointed out) you may want to compare the pipe code with the new zerocopy-pipe one (the one that IMHO has a chance to decreases parallelism)
Quoted 4 lines
having all the pages locked in memory is not a necessary condition
for the applicability of communication mechanisms based on capabilities. Simply, it make it easier to write the code and does not make me crazy with the Linux swapping system.
ok ;)
Overall my point is that the best is to keep the ram mapped in both tasks at the same time and to use the kernel only for synchronization (i.e. the wakeup/schedule calls in your code and to remove the pinning/ pte mangling enterely from the design) and the futex provides a more efficient synchronization since it doesn't even enter kernel space if the writer completes before the reader start and the reader completes before the writer starts again (so it has a chance to be better than any other kernel base scheme that is always forced to enter kernel even in the very best case).
Andrea
/*
* If you refuse to depend on closed software for a critical
* part of your business, these links may be useful:
*
* rsync.kernel.org::pub/scm/linux/kernel/bkcvs/linux-2.5/
* rsync.kernel.org::pub/scm/linux/kernel/bkcvs/linux-2.4/
* http://www.cobite.com/cvsps/
*
* svn://svn.kernel.org/linux-2.6/trunk
* svn://svn.kernel.org/linux-2.4/trunk
*/
Am Wednesday 10 September 2003 06:59 pm schrieb Andrea Arcangeli:
Hi,
Quoted 3 lines
design that I'm suggesting. Obviously lots of apps are already using this design and there's no userspace API simply because that's not needed.
HPC people have investigated High performance IPC many times basically it boils down to:
1. Userspace is much more efficient than kernel space. So efficient implementions avoid kernel space even for message transfers over networks (e.g. DMA directly to userspace).
2. The optimal protocol to use and the number of copies to do is depending on the message size.
Small messages are most efficiently handled with a single/dual copy (short protocol / eager protocol) and large messages are more efficient with single/zero copy techniques (get protocol) depending if a network is involved or not.
Traditionally in a networked environment single copy means PIO and zero copy means DMA when using network hardware.
The idea is while DMA has much higher bandwidth than PIO DMA is more expensive to initiate than PIO. So DMA is only useful for large messages.
In the local SMP case there do exist userspace APIs like MPI which can do single copy Message passing at memory speed in pure userspace since many years.
The following PDF documents a measurement where the communication between two processes running on different CPUs in an SMP system is exactly the memcpy bandwidth for large messages using a single copy get protocol.
http://ipdps.eece.unm.edu/1999/pc-now/takahash.pdf
Numbers from a Dual P-II-333, Intel 440LX (100MB/s memcpy)
eager get
min. Latency µs 8.62 9.98
max Bandwidth MB/s 48.03 100.02
half bandwith point KB 0.3 2.5
You can easily see that the eager has better latency for very short messages and that the get has a max bandwidth beeing equivalent of a memcpy (single copy).
True zero copy has unlimited (sigh!) bandwidth within an SMP and does not really make sense in contrast to a network.
Regards,
-- martin
Dipl.-Phys. Martin Konold
e r f r a k o n
Erlewein, Frank, Konold & Partner - Beratende Ingenieure und Physiker Nobelstrasse 15, 70569 Stuttgart, Germany
fon: 0711 67400963, fax: 0711 67400959
email: [email protected]
Quoted 23 lines · Martin Konold
Am Wednesday 10 September 2003 06:59 pm schrieb Andrea Arcangeli:
Hi,
Quoted 3 lines
design that I'm suggesting. Obviously lots of apps are already using this design and there's no userspace API simply because that's not needed.
HPC people have investigated High performance IPC many times basically it boils down to:
1. Userspace is much more efficient than kernel space. So efficient implementions avoid kernel space even for message transfers over networks (e.g. DMA directly to userspace).
2. The optimal protocol to use and the number of copies to do is depending on the message size.
Small messages are most efficiently handled with a single/dual copy (short protocol / eager protocol) and large messages are more efficient with single/zero copy techniques (get protocol) depending if a network is involved or not.
Quoted 5 lines
Traditionally in a networked environment single copy means PIO and zero copy means DMA when using network hardware.
The idea is while DMA has much higher bandwidth than PIO DMA is more expensive to initiate than PIO. So DMA is only useful for large messages.
agreed.
Quoted 2 lines
In the local SMP case there do exist userspace APIs like MPI which can do
btw, so far we were only discussing IPC in a local box (UP or SMP or NUMA) w/o networking involved. Luca's currnet implementation as well was only working locally.
Quoted 16 lines
single copy Message passing at memory speed in pure userspace since many years.
The following PDF documents a measurement where the communication between two processes running on different CPUs in an SMP system is exactly the memcpy bandwidth for large messages using a single copy get protocol.
http://ipdps.eece.unm.edu/1999/pc-now/takahash.pdfNumbers from a Dual P-II-333, Intel 440LX (100MB/s memcpy)
eager get
min. Latency µs 8.62 9.98
max Bandwidth MB/s 48.03 100.02
half bandwith point KB 0.3 2.5
Quoted 6 lines
You can easily see that the eager has better latency for very short messages and that the get has a max bandwidth beeing equivalent of a memcpy (single copy).
True zero copy has unlimited (sigh!) bandwidth within an SMP and does not really make sense in contrast to a network.
if you can avoid to enter kernel, you'd better do that, because entering kernel will take much more time than the copy itself.
with the shm/futex approch you can also have a ring buffer to handle parallelism better while it's at the same time zerocopy and enterely userspace based in the best case (thought that's not the common case).
thanks,
Andrea
/*
* If you refuse to depend on closed software for a critical
* part of your business, these links may be useful:
*
* rsync.kernel.org::pub/scm/linux/kernel/bkcvs/linux-2.5/
* rsync.kernel.org::pub/scm/linux/kernel/bkcvs/linux-2.4/
* http://www.cobite.com/cvsps/
*
* svn://svn.kernel.org/linux-2.6/trunk
* svn://svn.kernel.org/linux-2.4/trunk
*/
Am Wednesday 10 September 2003 08:01 pm schrieb Andrea Arcangeli:
Hi Andreas,
Quoted 10 lines
Quoted 2 lines
The idea is while DMA has much higher bandwidth than PIO DMA is more expensive to initiate than PIO. So DMA is only useful for large messages.
agreed.
Quoted 1 line
In the local SMP case there do exist userspace APIs like MPI which can do
btw, so far we were only discussing IPC in a local box (UP or SMP or NUMA) w/o networking involved. Luca's currnet implementation as well was only working locally.
Yes, and I claim that the best you can get for large messages is a plain single copy userspace implementation as already implemented by some people using the MPI API.
Quoted 5 lines
Quoted 2 lines
True zero copy has unlimited (sigh!) bandwidth within an SMP and does not really make sense in contrast to a network.
if you can avoid to enter kernel, you'd better do that, because entering kernel will take much more time than the copy itself.
Yes, doing HPC the kernel may only be used to intialize the intial communication channels (e.g. handling permissions etc.). The kernel must be avoided for the actual communication by any means.
Quoted 2 lines
with the shm/futex approch you can also have a ring buffer to handle parallelism better while it's at the same time zerocopy
How fast will you get? I think you will get the bandwidth of a memcpy for large chunks?!
This is imho not really zerocopy. The data has to travel over the memory bus involving the CPU so I would call this single copy ;-)
Quoted 2 lines
and enterely
userspace based in the best case (thought that's not the common case).
Yes a userspace library using the standard MPI API is the proven best approach and freely downloadable from
http://www.pccluster.org/score/dist/pub/score-5.4.0/source/score-5.4.0.mpi.tar.gz
Regards,
-- martin
Dipl.-Phys. Martin Konold
e r f r a k o n
Erlewein, Frank, Konold & Partner - Beratende Ingenieure und Physiker Nobelstrasse 15, 70569 Stuttgart, Germany
fon: 0711 67400963, fax: 0711 67400959
email: [email protected]
Quoted 9 lines · Martin Konold
Am Wednesday 10 September 2003 08:01 pm schrieb Andrea Arcangeli:
Quoted 3 lines
with the shm/futex approch you can also have a ring buffer to handle parallelism better while it's at the same time zerocopy
How fast will you get? I think you will get the bandwidth of a memcpy for large chunks?!
This is imho not really zerocopy. The data has to travel over the memory bus involving the CPU so I would call this single copy ;-)
Even with zerocopy, you have to build the message somehow. If process A builds a message and passes it to process B, then then isn't that as efficient as you can get with message passing? How does MPI do any better?
However, if both processes directly map the same memory and use it directly (without "messages" as such), then I would see *that* as zerocopy.
Chris
Signature · 4 lines
Chris Friesen | MailStop: 043/33/F10 Nortel Networks | work: (613) 765-0557 3500 Carling Avenue | fax: (613) 765-2986 Nepean, ON K2H 8E9 Canada | email: [email protected]
Inappropriate signatures
In reply to Andrea ArcangeliDear Andrea,
We're providing the service which enables all of the below and without our good will that service is at risk. You're publicly slamming the providers of that service.
If you want to do that, that's your right, but that leads us to ask:
- wasn't the deal that we do the gateway and you stop whining?
- why should we provide this gateway service at all if there is whining?
- why shouldn't we firewall you off since you are whining?
- or if firewalling fails, put in a day or two delay in the gateway?
Quoted 11 lines
/*
* If you refuse to depend on closed software for a critical
* part of your business, these links may be useful:
*
* rsync.kernel.org::pub/scm/linux/kernel/bkcvs/linux-2.5/
* rsync.kernel.org::pub/scm/linux/kernel/bkcvs/linux-2.4/
* http://www.cobite.com/cvsps/
*
* svn://svn.kernel.org/linux-2.6/trunk
* svn://svn.kernel.org/linux-2.4/trunk
*/
Signature · 2 lines
--- Larry McVoy lm at bitmover.com http://www.bitmover.com/lm
Re: Inappropriate signatures
Quoted 3 lines
Quoted 3 lines
* rsync.kernel.org::pub/scm/linux/kernel/bkcvs/linux-2.5/
* rsync.kernel.org::pub/scm/linux/kernel/bkcvs/linux-2.4/
* http://www.cobite.com/cvsps/
Oh, thanks! I didn't know about those links and have been using the daily snapshots from www.kernel.org's front page.
Those URLs (*and* BitKeeper ones) really should appear on or near the www.kernel.org front page, near all the list of snapshots etc.
-- Jamie
rsync head? [was inappropriate signatures]
In reply to Larry McVoyQuoted 1 line · Larry McVoy
Quoted 1 line
* rsync.kernel.org::pub/scm/linux/kernel/bkcvs/linux-2.5/
cvs/bk/svn/bz2? How about just plain text instead?
How about an rsync to the latest uncompressed source tree?
rsync.kernel.org::pub/linux/kernel/head?
Re: Inappropriate signatures
In reply to Larry McVoyHi!
Quoted 2 lines
We're providing the service which enables all of the below and without our good will that service is at risk.
Eh? You are providing a service and he provides you advertising. I can't see anything about slamming you. I guess that Andrea does not think about kernel developing as a business, so it is not really targeted at you.
But anyway its *his* signature.
Pavel
Quoted 11 lines
Quoted 11 lines
/*
* If you refuse to depend on closed software for a critical
* part of your business, these links may be useful:
*
* rsync.kernel.org::pub/scm/linux/kernel/bkcvs/linux-2.5/
* rsync.kernel.org::pub/scm/linux/kernel/bkcvs/linux-2.4/
* http://www.cobite.com/cvsps/
*
* svn://svn.kernel.org/linux-2.6/trunk
* svn://svn.kernel.org/linux-2.4/trunk
*/
Signature · 2 lines
When do you have a heart between your knees? [Johanka's followup: and *two* hearts?]
Re: Inappropriate signatures
Other people may not agree with your view on this one Pavel. Most people read that signature and saw it as a negative comment about BitKeeper.
People have told me they believe that if BitMover isn't getting benefit from the free use of BK, free BK will go away. People don't want to have to depend on my goodwill, they want BitMover to derive benefit so that my goodwill doesn't matter, it's just smart business to give BK away.
If that is really what people here think then that means there has to be some benefit for BitMover. One of the benefits is that we get to say that the kernel team uses it and get some marketing advantage out of that. But that benefit diminishes if what people are saying is negative.
It makes sense that people are uneasy about depending on BK given the amount of work it takes to provide it and the amount of grief we take for providing it. I don't know why I didn't see that earlier, it's an unstable situation.
I know there are some people who will never be happy until everything is GPLed, I can't help those people other than provide the gateway. In return, those people need to stop whining, the gateway has to be enough.
For the rest of the people, I'm looking for suggestions on how to make this situation more stable. It took me a while but I can see why you are nervous, I'd be nervous in your position. I'm nervous about doing any real marketing of the kernel's use of BK because I figured it would lead to more flame wars. I'm starting to think that if we were doing that it might actually lead to less flames, based on the theory that we would then need you so you continue to get BK for free. If you have an opinion on that I'd like to know it.
Quoted 28 lines · Pavel Machek
Hi!
Quoted 2 lines
We're providing the service which enables all of the below and without our good will that service is at risk.
Eh? You are providing a service and he provides you advertising. I can't see anything about slamming you. I guess that Andrea does not think about kernel developing as a business, so it is not really targeted at you.
But anyway its *his* signature.
PavelQuoted 11 lines
Quoted 11 lines
/*
* If you refuse to depend on closed software for a critical
* part of your business, these links may be useful:
*
* rsync.kernel.org::pub/scm/linux/kernel/bkcvs/linux-2.5/
* rsync.kernel.org::pub/scm/linux/kernel/bkcvs/linux-2.4/
* http://www.cobite.com/cvsps/
*
* svn://svn.kernel.org/linux-2.6/trunk
* svn://svn.kernel.org/linux-2.4/trunk
*/Signature · 2 lines
When do you have a heart between your knees? [Johanka's followup: and *two* hearts?]
Signature · 2 lines
--- Larry McVoy lm at bitmover.com http://www.bitmover.com/lm