Transcript ppt

Programming Project #3
Message Passing System
CS-502 Operating Systems
Fall 2006
CS-502 Fall 2006
Project 3, Message
Passing System
1
Objective
• To gain experience programming and
testing synchronization and IPC operations
• To gain experience with synchronization &
memory management in the Linux Kernel
• (Possibly) to learn to use kdb, the kernel
debugger
CS-502 Fall 2006
Project 3, Message
Passing System
2
Project
• To build and test a message-passing system
for Inter-process Communication among
separate address spaces
– Library interface for message-passing functions
– Kernel system call to actually pass messages
– Test program to exercise the message passing
system
CS-502 Fall 2006
Project 3, Message
Passing System
3
Message Passing Interface
int CreateMailbox(int msgSize, int maxMsgs,
long* mboxID);
int DeleteMailbox(void);
int SendMsg(long toID, void* msg, int len,
boolean noBlock);
int ReceiveMsg(long* fromID, void* msg,
int* len, boolean noBlock);
int ManageMailbox(int fcn, int* result);
CS-502 Fall 2006
Project 3, Message
Passing System
4
Mailboxes
• Each mailbox holds fixed size messages up to
msgSize in length
• Actual messages may be shorter but still take up msgSize bytes
• Multiple senders, one receiver per mailbox
• Sender’s mboxID automatically attached to each msg
• Mailbox associated with process or thread
stored in (or pointed to) by task_struct
• Only one mailbox per task
• Only creating task may receive, delete, or manage
• mboxID
• maxMsgs included to simplify this project
• In real life, mailbox would grow dynamically to global max.
CS-502 Fall 2006
Project 3, Message
Passing System
5
Messages
• Sent to mboxID of recipient
• Tattooed by system with mboxID of sender
• (may include timestamp for debugging purposes)
• uninterpreted sequence of len bytes  msgSize
• Received in FIFO order
•
mboxID
of sender and len returned with message
• Blocking
• If mailbox is full on SendMsg
• If mailbox is empty on ReceiveMsg
• Non-blocking if noBlock = TRUE; check error code
CS-502 Fall 2006
Project 3, Message
Passing System
6
Managing Mailboxes
int ManageMailbox(int fcn, int* result);
•
fcn = STOP
/* 1 */
• Stop receiving messages (e.g., prior to deleting)
•
fcn = START
/* 2 */
• Start receiving messages (e.g., restart after STOP)
• Default after CreateMailbox
•
fcn = COUNT
/* 3 */
• Return result = number of un-read messages in mailbox
• Useful after STOP, prior to delete
• Other functions as needed
• Share with class if you believe another function is needed!
CS-502 Fall 2006
Project 3, Message
Passing System
7
Possible Error Returns
• Mailbox full
• Invalid arguments
• Non-blocking send
• Mailbox empty
• all
• Mailbox not empty
• Non-blocking receive
• Invalid mailbox ID,
Mailbox is stopped,
Message too long
• On delete
• Mailbox too large
• msgSize, maxMsgs
• …
• On send
• Fill in other error
checking as needed
• No mailbox
• On receive, manage
CS-502 Fall 2006
Project 3, Message
Passing System
8
Kernel Implementation
• Recommend one system call for all mailbox
functions
• Kernel allocates slab to hold messages of
mailbox
• Mailboxes with same size message share a slab
• Common freelist per slab
• Sending allocates new message from freelist
• Receiving returns empty message to freelist
CS-502 Fall 2006
Project 3, Message
Passing System
9
Kernel Implementation (continued)
• Send
•
•
•
•
Allocate new message from freelist
copy_from_user to copy message body into kernel
Fill in other details
Link to mailbox
• Receive
•
•
•
•
CS-502 Fall 2006
Unlink from mailbox
copy_to_user to copy message body to caller
Return other details
De-allocate message to freelist
Project 3, Message
Passing System
10
Locking in the Kernel
• Slab
• Needs to be locked to allocate and de-allocate messages
• Mailbox
• Needs to be locked to link and unlink messages
• Also to change state (START, STOP)
• Remember – the Linux Kernel is fully preemptive!
• System call may be preempted before completion
• Interrupt may schedule another process at any time
• Interrupt may manage shared resources
– Due to support for symmetric multi-processing
CS-502 Fall 2006
Project 3, Message
Passing System
11
Robert Love says …
• It is a major bug if …
– An interrupt occurs to access a resource while
kernel code is also manipulating that resource
– Kernel code is preempted while accessing a
shared resource
– Kernel code sleeps while in the middle of a
critical section
– Two processors access same date at same time
• Implementing locking is not hard
• Tricky part is identifying what to lock.
CS-502 Fall 2006
Project 3, Message
Passing System
12
Locking Resources
• Atomic operations
• atomic_set, atomic_add, etc.
• asm/atomic.h
• Spin locks
• spinlock_t mb_lock = SPIN_LOCK_UNLOCKED
• spin_lock(&mb_lock), spin_unlock(&mb_lock)
• linux/spinlock.h
• (also reader-writer spinlocks)
• Kernel semaphores
• If you need to sleep while waiting
• asm/semaphore.h
CS-502 Fall 2006
Project 3, Message
Passing System
13
Synchronization Suggestions
• Sending and Receiving to/from mail box are
Producer-Consumer functions
• Use semaphores to block if full or empty
• Linking & Unlinking messages, slab
allocation, etc. are mutex critical sections
• Use spin lock to protect
• Adding, deleting, managing a mailbox is
???
• What should be used to protect it?
• Reference count for number of mailboxes in slab
CS-502 Fall 2006
Project 3, Message
Passing System
14
Memory Allocation Resources
• kmalloc(), kfree()
• linux/slab.h
• Similar to malloc() & free(), but with flags
• Also vmalloc()
– slight performance hit but does not require physically
contiguous pages
• Slab allocator
• kmem_cache_t* kmem_cache_create()
• int kmem_cache_destroy()
• void* kmem_cach_alloc()
• void kmem_cache_free()
CS-502 Fall 2006
Project 3, Message
Passing System
15
Example of Cache Usage
kmem_cache_t* task_struct_cachep;
task_struct_cachep =
kmem_cache_create(…);
struct task_struct* tsk;
tsk =
kmem_cache_alloc(task_struct_cachep,…);
if (!tsk) {return error};
kmem_cache_free(tast_struct_cachep, tsk);
int err = kmem_cache_destroy(
task_struct_cachep);
CS-502 Fall 2006
Project 3, Message
Passing System
16
Testing
• Fork multiple processes
• Create mailboxes, exchange mailbox IDs
• Randomly send messages to each other
• Payload must be self identifying
• Acknowledge received messages
• Test extreme conditions
• E.g., fill up mailbox
CS-502 Fall 2006
Project 3, Message
Passing System
17
Debugging
• Start with clean kernel tree
• Recommended settings
– Perhaps a clean VM!
• You may use printk()
– Takes arguments like
printf()
• You may try kdb, the
Kernel Debugger
– Already part of kernel
source tree
– See man pages in
Documentation/kdb
– Built-in Kernel
Debugger support
– KDB off by default
– Debug memory
allocations
– Compile kernel with
debug info
– Compile kernel with
frame pointers
– kobject debugging
– …
– Select Kernel hacking
during make xconfig
CS-502 Fall 2006
Project 3, Message
Passing System
18
KDB Manual pages
• PDF copies on-line at
www.cs.wpi.edu/~cs502/f06/KDB_Documentation
CS-502 Fall 2006
Project 3, Message
Passing System
19
Submission
• Submit using web-based turnin program
– http://turnin.cs.wpi.edu:8088/servlets/turnin/turnin.ss
• Include
–
–
–
–
–
Write up explaining implementation and testing
One patch file, plus source of test program
Starting point for your kernel tree
Test results
Put your name on all documents and at top of
every edited file!
CS-502 Fall 2006
Project 3, Message
Passing System
20
Due Dates
• Project due at start of class, Monday, November 6
• Pace yourself:–
– October 23:–
• Design of mailbox, sending & receiving in user space
• Test using multiple threads, user-space semaphores, etc.
– October 30:–
• Port design into kernel space, use kernel synchronization and memory
functions
• Test using multiple processes
– November 6
• Extra credit: Allow mailboxes of same size to share a slab
• Report to instructor any difficulties
See also
http://web.cs.wpi.edu/~cs502/e06/Project%202%20(Threads%20and
%20Mailboxes).htm
CS-502 Fall 2006
Project 3, Message
Passing System
21
Questions?
CS-502 Fall 2006
Project 3, Message
Passing System
22