/* TMIPC.c, Copyright (c) by , Swiss Federal Institute of Technology, Computer Engineering and Networks Laboratory. TOPSY -- A Teachable Operating System. Implementation of a tiny and simple micro kernel for teaching purposes. For further information, please visit http://www.tik.ee.ethz.ch/~topsy This software is provided under the terms of the GNU General Public Licence. A full copy of the GNU GPL is provided in the file COPYING found in the development root of Topsy. */ /* File: $Source: /usr/drwho/vault/cvs/topsy/Topsy/Threads/TMIPC.c,v $ Author(s): Affiliation: ETH Zuerich, TIK Version: $Revision: 1.49 $ Creation Date: Last Date of Change: $Date: 2000/03/31 17:50:40 $ by: $Author: gfa $ $Log: TMIPC.c,v $ Revision 1.49 2000/03/31 17:50:40 gfa Merged with /Net from several term projects Revision 1.48 1999/12/13 21:48:33 ruf GNU General Public Licence Update Revision 1.47 1999/10/29 14:53:26 jeker *** empty log message *** Revision 1.46 1999/10/21 20:22:30 jeker first commit for the R4k support Revision 1.45 1999/06/06 20:55:08 jeker putting everything together for Topsy 2.0 Revision 1.44 1999/01/08 22:07:21 cjeker more bug fixes Revision 1.43 1999/01/08 21:28:01 cjeker moved branchDelayBit handling to TMHalAsm.S Revision 1.42 1998/04/11 20:21:42 gfa uses longCopy for message copying * Revision 1.41 97/04/21 07:25:01 conrad * cleanup * * Revision 1.40 1997/04/21 07:04:00 conrad * better error comments * * Revision 1.39 1997/04/18 16:33:55 conrad * *** empty log message *** * * Revision 1.38 1997/04/14 21:08:40 conrad * *** empty log message *** * * Revision 1.37 1997/04/13 16:57:34 conrad * Some changes from cc, and then from gfa (due to not opportune lock) * Problem with the fifth parameter (branch delay bit) test * * Revision 1.36 1997/04/09 16:22:36 conrad * *** empty log message *** * * Revision 1.35 1997/04/06 18:56:33 gfa * adjusted calls to TMHal * * Revision 1.34 1997/04/04 18:19:42 gfa * removed warning about missing thread-id. since the kernel-scratch-register * bug was fixed this is no longer useful... * * Revision 1.33 1997/04/01 16:23:31 conrad * *** empty log message *** * * Revision 1.32 1997/03/31 20:30:08 gfa * changed calls to ready/blocked * and schedule() * * Revision 1.31 1997/03/24 12:42:46 conrad * *** empty log message *** * * Revision 1.30 1997/03/24 10:58:03 conrad * cosmetics * * Revision 1.29 1997/03/21 19:14:06 conrad * cosmetics * * Revision 1.28 1997/03/21 17:23:47 conrad * cosmetics * * Revision 1.27 1997/03/21 13:02:49 conrad * *** empty log message *** * * Revision 1.26 1997/03/20 17:36:08 conrad * If a recv is performed on an inexisting thread, then it returns with * a TM_MESGRECVFAILED * * Revision 1.25 1997/03/20 14:01:20 conrad * Adding of the freeBlockedThreads() function * * Revision 1.24 1997/03/19 21:36:06 conrad * cosmetics * * Revision 1.23 1997/03/18 16:27:45 conrad * cosmetics * * Revision 1.22 1997/03/16 22:12:04 gfa * *** empty log message *** * * Revision 1.21 1997/03/14 16:34:05 conrad * cosmetics * * Revision 1.20 1997/03/14 11:04:25 conrad * Removal of message queue dumping * * Revision 1.19 1997/03/14 10:51:17 conrad * Adding of debug information * * Revision 1.18 1997/03/13 23:56:26 gfa * fixed senders thread id in messages * * Revision 1.17 1997/03/13 14:25:02 conrad * Simplification of the pending structure * Introduction of three states for pending buffer (2 were not sufficient) * * Revision 1.16 1997/03/12 17:53:48 conrad * Debugging version * * Revision 1.15 1997/03/10 15:30:50 conrad * PANIC if branch delay bit set in msgDispatcher * * Revision 1.14 1997/03/07 13:00:38 conrad * Adding Error module * * Revision 1.13 1997/03/04 16:56:01 conrad * minor changes * * Revision 1.12 1997/02/28 08:10:51 conrad * Setting msgPendingFlag to TRUE ... * * Revision 1.11 1997/02/27 14:38:08 conrad * minor changes * * Revision 1.10 1997/02/26 17:34:02 conrad * cleaning * * Revision 1.9 1997/02/25 16:58:14 conrad * standalone tested version (at least the list management) * * Revision 1.8 1997/02/24 21:35:02 conrad * incomplete version * * Revision 1.7 1997/02/23 17:43:01 gfa * corrected hashlist get parameter order * * Revision 1.6 1997/02/21 16:52:29 conrad * very incomplete status due to major changes ... * * Revision 1.5 1997/02/21 09:15:13 conrad * Intermediate status (not yet completed) * * Revision 1.4 1997/02/19 17:46:24 conrad * *** empty log message *** * * Revision 1.3 1997/02/18 18:28:04 conrad * Introduction of tm-include.h * * Revision 1.2 1997/02/18 17:25:37 conrad * *** empty log message *** * * Revision 1.1 1997/02/12 15:35:07 conrad * Initial revision * */ #include "TMIPC.h" #include "TMThread.h" #include "TMScheduler.h" #include "TMHal.h" #include "Support.h" #include "HashList.h" #include "List.h" /* Global variables */ extern HashList threadHashList; /* Hash list of all threads */ extern List threadList; /* Linear list of all threads */ /* * When a thread exits (either exited or killed), a linear search is performed * among all receive-blocked threads to make them ready again if they expected * anything from the no longer existing thread (no infinite waiting for msg!). */ void ipcFreeBlockedThreads( ThreadId exitThreadId) { Thread* threadPtr; if (listGetFirst( threadList, (void**)&threadPtr) != LIST_OK) { PANIC("listGetFirst() did not work"); } while (threadPtr != NULL) { if (threadPtr->schedInfo.status == BLOCKED) { if (threadPtr->msgQueue.threadIdPending == exitThreadId) { /* threadPtr must be re-activated with a failed return value */ tmSetReturnValue(threadPtr->contextPtr, TM_MSGRECVFAILED); schedulerSetReady(threadPtr); } } /* else if (threadPtr->schedInfo.status == READY) { * } else { * } */ /* not used at the moment, make it easier for the compiler ;-) */ listGetNext( threadList, (void**)&threadPtr); } } /* * Initialisation of the message queue */ void initMsgQueue( MessageQueue* queuePtr) { int i; queuePtr->freeList = 0; queuePtr->busyList = -1; for (i=0;ictrl[i] = (i+1) % MAXNBMSGINQUEUE; queuePtr->ctrl[MAXNBMSGINQUEUE-1] = -1; queuePtr->msgPendingStatus = NOT_WAITING; } /* * Check if the pending flag can be removed. * This procedure is only invoked by the scheduler before setting a new * thread as the next to be scheduled. If the pending flag for the new * thread is set, then it can be removed, as it is guaranteed that the * new thread will then have access to its message. */ void ipcResetPendingFlag(Thread* threadPtr) { threadPtr->msgQueue.msgPendingStatus = NOT_WAITING; } /* * A new message is inserted in the queue of the receiving thread */ static int addMessageInQueue(Thread* threadPtr, Message* msgPtr) { MessageQueue* queue = &(threadPtr->msgQueue); int oldFreeList = queue->freeList; int tmpBusyList = queue->busyList; Message threadKillMsg = {TMTHREADID, TM_KILL, {{NULL, NULL, NULL}}}; if (queue->freeList == -1) { /* Message queue full */ ERROR("addMessageInQueue(): msg queue is full"); /* If the thread is in user space, then it is killed */ if (THREAD_MODE(threadPtr->id) == USER) { ioConsolePutString("(thread "); ioConsolePutString(threadPtr->name); ioConsolePutString(" will be killed)\n"); threadKillMsg.msg.tmKill.id = threadPtr->id; kSend( TMTHREADID, &threadKillMsg); } return TM_MSGQUEUEOVERFLOW; } else { /* Copy message at position queue->freeList */ byteCopy( &(queue->msg[queue->freeList]), msgPtr, sizeof(Message)); /* Updating queue->freeList */ queue->freeList = queue->ctrl[queue->freeList]; /* Updating queue->busyList */ if (queue->busyList == -1) { queue->busyList = oldFreeList; queue->ctrl[oldFreeList] = -1; } else { while (queue->ctrl[tmpBusyList] != -1) { tmpBusyList = queue->ctrl[tmpBusyList]; } queue->ctrl[tmpBusyList] = oldFreeList; queue->ctrl[oldFreeList] = -1; } } return TM_OK; } /* * A single message is retrieved from the message queue. * Message must be of type msgPtr->id and sender msgPtr->from as * requested by the tmMsgRecv() call. */ static int getMessageFromQueue( Thread* threadPtr, /* thread about to receive a msg */ Message* msgPtr) /* message structure */ { MessageQueue* queue = &(threadPtr->msgQueue); int tmpBusyList = queue->busyList; int tmp = queue->busyList; MessageId expectedMsgId = msgPtr->id; ThreadId expectedThreadId = msgPtr->from; Boolean notFound = TRUE; Message msg; if (queue->busyList == -1) { return TM_NOSUCHMESSAGE; } while (tmpBusyList != -1 && notFound) { /* Check if message 'msg' at position 'tmpBusyList' matches request */ msg = queue->msg[tmpBusyList]; if ( expectedMsgId == ANYMSGTYPE && expectedThreadId == ANY) { notFound = FALSE; } else if (expectedMsgId==ANYMSGTYPE && expectedThreadId==msg.from) { notFound = FALSE; } else if ( expectedMsgId == msg.id && expectedThreadId == ANY) { notFound = FALSE; } else if ( expectedMsgId == msg.id && expectedThreadId == msg.from) { notFound = FALSE; } if (notFound == FALSE) { byteCopy( msgPtr, &msg, sizeof(Message)); /* Update of queue->busyList */ if (tmpBusyList == queue->busyList) { queue->busyList = queue->ctrl[tmpBusyList]; queue->ctrl[tmpBusyList] = queue->freeList; queue->freeList = tmpBusyList; } else { while ( queue->ctrl[tmp] != tmpBusyList) { tmp = queue->ctrl[tmp]; } queue->ctrl[tmp] = queue->ctrl[tmpBusyList]; /* Update of queue->freeList */ queue->ctrl[tmpBusyList] = queue->freeList; queue->freeList = tmpBusyList; } } tmpBusyList = queue->ctrl[tmpBusyList]; } if (notFound) { return TM_NOSUCHMESSAGE; } else { return TM_OK; } } Error kSend(ThreadId destThreadId, Message* msgPtr) { Thread* destThreadPtr; Error errorCode = TM_OK; MessageQueue* queue; /* used for simplification in below expressions */ Boolean copyInTmp = FALSE; /* help flag */ /* Lookup in hash table to find pointer onto destination thread */ if ((hashListGet( threadHashList, (void**)(&destThreadPtr), destThreadId)) != HASHOK) { return TM_THREADNOTFOUND; } switch( destThreadPtr->schedInfo.status) { case RUNNING: case READY: /* Destination thread is not waiting for a message, copy in queue */ errorCode = addMessageInQueue( destThreadPtr, msgPtr); break; case BLOCKED: /* Thread is expecting a message, check if there is a match */ queue = &(destThreadPtr->msgQueue); /* Check status of pending message */ if (queue->msgPendingStatus==FILLED || queue->msgPendingStatus==NOT_WAITING) { copyInTmp = FALSE; /* do not overwrite previous unread message */ } else if ( queue->threadIdPending == ANY && queue->msgIdPending == ANYMSGTYPE) { copyInTmp = TRUE; } else if ( queue->threadIdPending == schedulerRunning()->id && queue->msgIdPending == ANYMSGTYPE) { copyInTmp = TRUE; } else if ( queue->threadIdPending == ANY && queue->msgIdPending == msgPtr->id) { copyInTmp = TRUE; } else if ( queue->threadIdPending == schedulerRunning()->id && queue->msgIdPending == msgPtr->id) { copyInTmp = TRUE; } if (copyInTmp) { queue->msgPendingStatus = FILLED; /* Message must be copied at the address stated in msgPendingPtr */ byteCopy( queue->msgPendingPtr, msgPtr, sizeof(Message)); /* here, we must adjust the Messages... */ /* We are on the way away from the Kernel */ msgAdjust(destThreadPtr, queue->msgPendingPtr, FALSE); /* The destination thread is set to READY status (wake up) */ schedulerSetReady( destThreadPtr); } else { /* Message has to be copied in message queue */ errorCode = addMessageInQueue( destThreadPtr, msgPtr); } break; } if (errorCode == TM_OK) { /* A new scheduling decision is necessary if a higher priority * thread has to become active */ schedule(); } return errorCode; } Error kRecv( Message* msgPtr, /* message structure (contains exp. * sender and type) */ Thread* threadPtr) /* thread wishing to receive a message */ { Error errorCode; MessageQueue* queuePtr = &(threadPtr->msgQueue); /* Check to see if the expected message is already in the queue */ if ((errorCode=getMessageFromQueue( threadPtr, msgPtr)) == TM_OK) { /* Expected message was copied in msgPtr */ /* here, we must adjust the Messages... */ /* We are on the way away from the Kernel */ msgAdjust(threadPtr, msgPtr, FALSE); return TM_OK; } else { /* The expected message has not yet arrived in the message queue */ queuePtr->msgPendingStatus = WAITING; /* thread waiting for a * special message */ queuePtr->msgPendingPtr = msgPtr; /* address where the message * is expected */ queuePtr->threadIdPending = msgPtr->from; /* expected message sender */ queuePtr->msgIdPending = msgPtr->id; /* expected message type */ return TM_NOSUCHMESSAGE; } } /* A SYSCALL exception occurred, thus either tmMsgSend() or tmMsgRecv() was * invoked with a message. */ int msgDispatcher( ThreadId fromId, /* thread that caused exception */ Message* msgPtr, /* message reference */ unsigned long int timeout,/* timeout for receiving */ MsgOpCode code) /* SYSCALL_SEND_OP/SYSCALL_RECV_OP */ { Error errorCode = TM_OK; Thread* threadPtr; Thread* fromThreadPtr; ThreadId to; /* Lookup in hash table to find pointer onto threadId */ if ((errorCode = hashListGet( threadHashList, (void**)(&threadPtr), fromId)) != HASHOK) { PANIC("msgDispatcher(): required thread id does not exist"); } switch (code) { case SYSCALL_SEND_OP: /* Filtering TM_YIELD: * No message is sent to the thread manager, as it would be obliged * to perform a new scheduling decision and a restoreContext() outside * of an exception context, which leads to tricky problems. * Instead, threadYield() is directly invoked from this point in an * exception context. */ if (msgPtr->id==TM_YIELD && msgPtr->from==TMTHREADID) { tmSetReturnValue(threadPtr->contextPtr, TM_MSGSENDOK); threadYield(); } else { to = msgPtr->from; msgPtr->from = fromId; /* copy sender id to msg */ if (kSend( to, msgPtr) != TM_OK ) { tmSetReturnValue(threadPtr->contextPtr, TM_MSGSENDFAILED); } else { /* message was successfully copied in messageQueue */ tmSetReturnValue(threadPtr->contextPtr, TM_MSGSENDOK); } /* A new scheduling decision was taken in kSend(), as kSend() may * be called from other modules, independently of msgDispatcher() */ } break; case SYSCALL_RECV_OP: /* Check if the expected threadId exists */ if ((hashListGet(threadHashList, (void**)(&fromThreadPtr),msgPtr->from) != HASHOK) && (msgPtr->from != ANY)) { tmSetReturnValue(threadPtr->contextPtr, TM_MSGRECVFAILED); } else { if (kRecv( msgPtr, threadPtr) != TM_OK ) { /* No corresponding message found, put receiver to sleep, * and make a new scheduling decision */ /*if (threadPtr->id > 0) { ioConsolePutString("thread id "); ioConsolePutInt(threadPtr->id); ioConsolePutString(" blocked, waiting\n"); }*/ schedulerSetBlocked(threadPtr); schedule(); } /* The expected message was copied in msgPtr */ tmSetReturnValue(threadPtr->contextPtr, TM_MSGRECVOK); break; } } return TM_OK; }