OSDev.org

The Place to Start for Operating System Developers
It is currently Sat Sep 26, 2020 10:14 am

All times are UTC - 6 hours




Post new topic Reply to topic  [ 16 posts ]  Go to page 1, 2  Next
Author Message
 Post subject: My IPC design
PostPosted: Wed Jan 06, 2010 4:45 pm 
Offline
Member
Member

Joined: Fri Oct 20, 2006 10:14 am
Posts: 313
I just thought how I can get a string that should be printed into the console from the process into my appserver. So I came up with this idea of my ipc design. It could be that this is the same as pipes are (I don´t really know how pipes are working).

So I will only have fixed size messages (max 20bytes) and all other things will be send over shared memory. I thought it would be a good idea to have a ring buffer as shared memory and the user process is writing into this ring buffer. It will call only into the kernel if the reader (appserver) isn´t active. So printf would write its string into the ring buffer and at the end of printf would eventually call the kernel and the kernel would wake up the reader (appserver). I think that this would be fast and safe on an uni cpu system and would scale well on a multi cpu system. I would use a flag so that the writer (printf) could test if the reader is already active and so it hasn´t to call into the kernel (so I save a kernel call). I could even make a special version for smp systems, so that when the writer has written the 1st data, that the reader is woken up and the work can be done at the same time.

My question is, what could I do better or is this a bad idea?


Top
 Profile  
 
 Post subject: Re: My IPC design
PostPosted: Wed Jan 06, 2010 6:12 pm 
Offline
Member
Member
User avatar

Joined: Tue Mar 24, 2009 8:11 pm
Posts: 1249
Location: Sunnyvale, California
I can't see any problems with that design, as long as you put it together correctly, of course. It sounds pretty similar to my IPC system, which I find works pretty well. One difference is that instead of true shared memory, I allow any process to send an entire page of memory as a message: it is simply unmapped in the sender and the receiver is allowed to map it optionally through a special call. There's no buffering overhead, and synchronization is completely implicit and safe. It also allows the receiver to redirect a message without copying anything.


Top
 Profile  
 
 Post subject: Re: My IPC design
PostPosted: Wed Jan 06, 2010 7:41 pm 
Offline
Member
Member

Joined: Thu Feb 26, 2009 1:45 am
Posts: 38
@FlashBurn : Make sure that the reciever can't get idle while the sender thinks it is active, i.e.
Code:
Sender checks active flag : YES
Clock tick
Scheduler comes bluntly in
Switch to reciever
Reciever finishes fetching last byte
Reciever checks if new bytes are there... NO
Reciever goes idle
Switch to sender
Sender writes bytes, but they'll never be read

If you check active flag *after* sending bytes and moving circular buffer's head, then it should be OK, but if I were you, I'd triple-check that no race condition might occur.

Also you should think about what might happen if a buggy / nasty sender overwrites some bytes before reciever gets them. Say you have an utf-8 terminal, and the sender writes the first byte of a multibyte string (say, 2 bytes), waits for the reciever to get first byte. It'll detect a multibyte char, and wait for the next byte to come in. Then the sender overwrites both bytes, first and second. The reciever thinks first byte is still the same and will skip some sanity checks on the first byte before looking up the character in the font table. Thus, you have pushed into the reciever a byte on which it hasn't done sanity checks, and that's a big door for privilege escalation.

@NickJohnson : Nice idea to allow processes to send a whole page :)


Top
 Profile  
 
 Post subject: Re: My IPC design
PostPosted: Thu Jan 07, 2010 2:27 am 
Offline
Member
Member

Joined: Fri Oct 20, 2006 10:14 am
Posts: 313
@js

Yeah I thought about the problem of the receiver getting idle when the sender thinks it is active, but I think this wont be a problem, the only thing that could occur is, that the sender thinks the receiver is idle, but the receiver gets active just as the sender finished the checking and so the sender will try to activate the receiver which is working.

I will write a library for using my ipc functions, so it could but it should not happen that there will be something going on I don´t want. The situation you are writing about should be possible, because the receiver will read the byte and will buffer it, so that the read pointer can be set to its new position (this is like a ring buffer works) and the receiver has to wait for a new byte of data or it is going to sleep until the sender reactivates it.


Top
 Profile  
 
 Post subject: Re: My IPC design
PostPosted: Thu Jan 07, 2010 5:08 am 
Offline
Member
Member

Joined: Mon Dec 21, 2009 6:03 pm
Posts: 164
@FlashBurn

"Anything that can go wrong will go wrong." -- Murphy's Law

Im gonna say this needs alot more thought when it comes to SMP.


Top
 Profile  
 
 Post subject: Re: My IPC design
PostPosted: Thu Jan 07, 2010 5:16 am 
Offline
Member
Member

Joined: Fri Oct 20, 2006 10:14 am
Posts: 313
On what problems do you think?


Top
 Profile  
 
 Post subject: Re: My IPC design
PostPosted: Thu Jan 07, 2010 5:28 am 
Offline
Member
Member
User avatar

Joined: Wed Oct 18, 2006 3:45 am
Posts: 9287
Location: On the balcony, watching the Swedish Chef
I think he's referring to the fact that race conditions are hard to detect, diagnose, and debug, and easy to create in a multithreaded environment...

_________________
"Certainly avoid yourself. He is a newbie and might not realize it. You'll hate his code deeply a few years down the road." - Sortie
[ My OS ] [ VDisk/SFS ]


Top
 Profile  
 
 Post subject: Re: My IPC design
PostPosted: Thu Jan 07, 2010 5:44 am 
Offline
Member
Member

Joined: Fri Oct 20, 2006 10:14 am
Posts: 313
That´s right, to make it more secure I could move the whole checking if receiver is working thing and setting the flags into the kernel, but this would make the code slower. I will see how I can solve this. I mean I know that I can´t guarantee that the sender isn´t going to write something undefined into the flags, but at the moment I don´t know if this would be a problem for the receiver. But moving this particular code into the kernel wouldn´t solve the problem that the sender could overwrite the data that the receiver hasn´t yet read. So I also could reside the code for flag handling in user mode. The only solution I could think of at the moment would be, that I need to call the kernel every time I want write something into the ring buffer this would be the safest method, but also the slowest.


Top
 Profile  
 
 Post subject: Re: My IPC design
PostPosted: Thu Jan 07, 2010 6:22 am 
Offline
Member
Member

Joined: Mon Dec 21, 2009 6:03 pm
Posts: 164
@FlashBurn

The battle of Trust(Security) Over Speed.

The overhead of having the IPC inside the kernel is most likely comparable to actually providing equal security in the current design :wink:

But then, i guess that depends on what your kernel is designed for.

MikeyB


Top
 Profile  
 
 Post subject: Re: My IPC design
PostPosted: Thu Jan 07, 2010 3:32 pm 
Offline
Member
Member

Joined: Fri Oct 20, 2006 10:14 am
Posts: 313
Maybe I will implement 2 variants of this system, one for speed one for safeness.

But I wonder what problems could appear if the sender would overwrite data, which the receiver hasn´t yet read? I mean it is the same as when I send a msg which only has garbage in it. So the damage which could be done is minimal, or am I wrong here? The only problem I see is that the receiver gets garbage and I don´t think that this is a security problem as it would be the same as I send garbage with the help of a msg.


Top
 Profile  
 
 Post subject: Re: My IPC design
PostPosted: Thu Jan 07, 2010 4:34 pm 
Offline
Member
Member

Joined: Sun Jan 06, 2008 8:41 am
Posts: 174
I think you have to really consider why you assume that it's not a problem with the receiver going idle after the sender has checked the receiver status. I don't think it's trivial to guarantee that this does not happen, especially not in a multiprocessor environment.

When it comes to the problem of overwritten message buffer you have to make sure that the data that the receiver has verified to be an acceptable message is the data that is actually processed. This may need to move some of the data from the buffer if you don't want to end up with a half-done work.

Performance wise I'm a little sceptic about the idea. If you're going to have address space separation of the processes (otherwise you can't protect the receiver from the sender anyway) you have to perform the context switch in kernel space (unless you have some kind of multiprocessor architecture).


Top
 Profile  
 
 Post subject: Re: My IPC design
PostPosted: Thu Jan 07, 2010 5:21 pm 
Offline
Member
Member

Joined: Fri Oct 20, 2006 10:14 am
Posts: 313
I will have 2 flags, one for an active writer and one for an active reader. So why should the reader go idle when the writer is still working!? Also has the writer to write a new value for its write position and if it does so, before it clears the flag for an active writer and the reader will 1st clear the flag that it is working and then will check if there is new data. So it could happen the the writer sends a "msg" to activate the write, but this is no problem. I will try to work it out on paper ;)

I think you haven´t got the whole picture. I will use the ring buffer like a msg buffer. So the reader will read some bytes out of the ring buffer and buffer these bytes somewhere to work with it, like if you would receive a msg and the kernel would copy it into user space.

The came up with this idea because I could not imagine a good way to send a string I want to print onto a console into my appserver. So I only have to write into this ring buffer and if it is "full" I will call the reader and would go into a waiting state, the reader then processes the data and would then activate the writer (only if the writer waits for the reader) which then can go on writing data into the buffer. It is easier this way, instead of calling the kernel to send a msg of a variable size, because the kernel then has to alloc mem for this msg, copy the data and then the reader has to call the kernel to get the size of the msg, allocate some mem and call the kernel again so that the kernel can copy the data into the readers address space. With my system the data is already in user space and no more kernel calling is needed, but the reader does need some sort of buffering. For my example of printing a string it would be enough to read the buffer byte by byte and display it. But for another situation the reader could also read the data in other sizes and the data will be copied into the buffer. The problem which could occur (especially on smp systems) is that when I reader is reading the data, that the writer could overwrite this data, but as I said, you can also have this problem with msgs (garbage data). The security should be no problem here and the problem should (and could) only appear if the writer (or reader) is doing all the data moving by its own and not with the help of my library functions.

I hope I could make my idea a little bit clearer. I´m still designing it and have not programmed any line of code.


Top
 Profile  
 
 Post subject: Re: My IPC design
PostPosted: Sat Jan 16, 2010 6:42 am 
Offline
Member
Member

Joined: Sun Jan 06, 2008 8:41 am
Posts: 174
What you seem to be looking for is kind of fast userspace semaphores which is fine. What basically the sender must do before he adds data is to wait for the space-available semaphore (and increase the data-available semaphore), the receiver does the opposite. If the semaphores are not a fast userspace variant you have to have a call to the kernel to do this.Then of course you may twist these semaphores to be more like ringbuffer put and get indices if you wish, the concept being more or less the same anyway. My main point was that if you're running on a traditional single-threaded processor core you're bound to have only one piece of code running at the same time and switching between them has to go via the context-switch code (which often is within the kernel) so IPC in this case has to involve the kernel one way or another.

BTW the sending of a message does not have to be as complicated as you write. You may have to have some kind of shared memory allocation mechanism, but besides that sending a message may be as easy as just transporting the pointer+length values (as long as we cope with the problem that both processes has direct access to the memory area).


Top
 Profile  
 
 Post subject: Re: My IPC design
PostPosted: Sat Jan 16, 2010 7:13 am 
Offline
Member
Member

Joined: Fri Oct 20, 2006 10:14 am
Posts: 313
To make my point clearer I take the example of printf. I don´t know how this works in OS´s like Linux or Windows, but the problem I have with this special function is, how can I get a string, of a length I don´t know, into my appserver? E.g.

Code:
printf("value of x: %d and of y: %d\n",x,y);


Either you make the whole string thing in userspace, so you have to allocate a buffer which is big enough and then you copy the string there and if you finished you call the kernel to send a msg with the string. Here the kernel now needs to allocate memory big enough in size to take the string and what else is needed for the msg and send it to the receiver.

Another way would be, call the kernel and send only the string till the "%". Then use a buffer and construct the string which is needed for "%d", call the kernel again. And so on. This would be the worst method.

So I would have a ringbuffer and I assume that the read and write pointer are at the same point. So I could write at least so much bytes into the buffer as the size of the ringbuffer. And I think for my above example of the printf function 4096bytes should be enough. So I would make only one call to the kernel which then could wake up the receiver which then could read byte by byte out of the ringbuffer and display it on screen. I could also make it so, that the sender gives up its timeslice and the priority of the receiver gets a boost, maybe this would make things faster on a one cpu system. And on a one cpu system you will have always context switches to get the code of the receiver run.

I know that is just another form of shared memory, but here the programmer hasn´t to do the work to get it synchronized.

The only disadvantage of this is that it is a one way communication. At the moment I don´t see a problem with that. Ok I wast at least 4kb of memory for every ringbuffer, but this shouldn´t be a problem. I think with a fixed sized msg you can do most things and when there is the need of bigger sizes you take the ringbuffer.

I think the advantage of my design is, that the user just calls a "put" function as often as he wishes and he hasn´t to deal with if the buffer is full or not, the user even wont notice if the "put" function gives up to the receiver. So I have only to do:

Code:
putchar(char c) {
put(bufHandle,c,1);
}


And the rest of handling the buffer and call the receiver is done at the "put" function. The only thing is that at the end of a printf, the user should call something like "flushBuffer" for the case that the buffer isn´t full. This however would make my implementation of printf in some way tricky, because I call myself if I need to do something like this:

Code:
printf("text: %s\n","Hello World!");


So maybe I find a way to resolve this.


Top
 Profile  
 
 Post subject: Re: My IPC design
PostPosted: Sat Jan 16, 2010 4:13 pm 
Offline
Member
Member

Joined: Mon Dec 21, 2009 6:03 pm
Posts: 164
I think one of us is confused (I wouldn't be surprised if its me).

From your example, The string length should be known before it hits the IPC.

I believe printf works by processing a fixed number of inputs (in this case 1, the first argument), then it builds the needed string by working down the stack where the other inputs are held.

The constructed string is THEN sent to whom ever its meant to go to. (I think this was your first description?)

As printf has now created a new section of memory with the full string in, How you "pass" this bit of memory is up to you.

I would also like to add that you mention about the producer "giving up its timeslice". This is handled by the scheduler (normally), So how are you going to let the kernel know about the state of ur ringbuffers?

MikeyB

edit

and also the wiki has some good stuff already on this. http://wiki.osdev.org/Eleanore_Semaphore
http://wiki.osdev.org/Message_Passing


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 16 posts ]  Go to page 1, 2  Next

All times are UTC - 6 hours


Who is online

Users browsing this forum: No registered users and 4 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group