From b16a88692a4cc2399549b82b72d4b38ba8797112 Mon Sep 17 00:00:00 2001 From: Jorrit Herder Date: Wed, 12 Oct 2005 15:08:23 +0000 Subject: [PATCH] New deadlock check at proc.c. New exit checks (stop IPC). --- kernel/ipc.h | 1 + kernel/proc.c | 89 ++++++++++++++++++++++++++++++++--------- kernel/system/do_exit.c | 6 ++- kernel/table.c | 5 +-- 4 files changed, 78 insertions(+), 23 deletions(-) diff --git a/kernel/ipc.h b/kernel/ipc.h index c8442f54d..4cef03e25 100644 --- a/kernel/ipc.h +++ b/kernel/ipc.h @@ -25,5 +25,6 @@ #define CHECK_PTR 0x0B /* 1 0 1 1 : validate message buffer */ #define CHECK_DST 0x05 /* 0 1 0 1 : validate message destination */ #define CHECK_SRC 0x02 /* 0 0 1 0 : validate message source */ +#define CHECK_DEADLOCK 0x03 /* 0 0 1 1 : check for deadlock */ #endif /* IPC_H */ diff --git a/kernel/proc.c b/kernel/proc.c index e54a51215..11e1b01f8 100755 --- a/kernel/proc.c +++ b/kernel/proc.c @@ -46,15 +46,16 @@ * interrupts to prevent race conditions. */ FORWARD _PROTOTYPE( int mini_send, (struct proc *caller_ptr, int dst, - message *m_ptr, unsigned flags) ); + message *m_ptr, unsigned flags)); FORWARD _PROTOTYPE( int mini_receive, (struct proc *caller_ptr, int src, - message *m_ptr, unsigned flags) ); -FORWARD _PROTOTYPE( int mini_notify, (struct proc *caller_ptr, int dst) ); - -FORWARD _PROTOTYPE( void enqueue, (struct proc *rp) ); -FORWARD _PROTOTYPE( void dequeue, (struct proc *rp) ); -FORWARD _PROTOTYPE( void sched, (struct proc *rp, int *queue, int *front) ); -FORWARD _PROTOTYPE( void pick_proc, (void) ); + message *m_ptr, unsigned flags)); +FORWARD _PROTOTYPE( int mini_notify, (struct proc *caller_ptr, int dst)); +FORWARD _PROTOTYPE( int deadlock, (int function, + register struct proc *caller, int src_dst)); +FORWARD _PROTOTYPE( void enqueue, (struct proc *rp)); +FORWARD _PROTOTYPE( void dequeue, (struct proc *rp)); +FORWARD _PROTOTYPE( void sched, (struct proc *rp, int *queue, int *front)); +FORWARD _PROTOTYPE( void pick_proc, (void)); #define BuildMess(m_ptr, src, dst_ptr) \ (m_ptr)->m_source = (src); \ @@ -99,6 +100,7 @@ message *m_ptr; /* pointer to message in the caller's space */ int function = call_nr & SYSCALL_FUNC; /* get system call function */ unsigned flags = call_nr & SYSCALL_FLAGS; /* get flags */ int mask_entry; /* bit to check in send mask */ + int group_size; /* used for deadlock check */ int result; /* the system call's result */ vir_clicks vlo, vhi; /* virtual clicks containing message to send */ @@ -150,12 +152,21 @@ message *m_ptr; /* pointer to message in the caller's space */ */ if (function & CHECK_DST) { if (! get_sys_bit(priv(caller_ptr)->s_ipc_to, nr_to_id(src_dst))) { - kprintf("sys_call: ipc mask denied %d sending to %d\n", - proc_nr(caller_ptr), src_dst); + kprintf("sys_call: ipc mask denied trap %d from %d to %d\n", + function, proc_nr(caller_ptr), src_dst); return(ECALLDENIED); /* call denied by ipc mask */ } } + /* Check for a possible deadlock for blocking SEND(REC) and RECEIVE. */ + if (function & CHECK_DEADLOCK) { + if (group_size = deadlock(function, caller_ptr, src_dst)) { + kprintf("sys_call: trap %d from %d to %d deadlocked, group size %d\n", + function, proc_nr(caller_ptr), src_dst, group_size); + return(ELOCKED); + } + } + /* Now check if the call is known and try to perform the request. The only * system calls that exist in MINIX are sending and receiving messages. * - SENDREC: combines SEND and RECEIVE in a single system call @@ -194,6 +205,56 @@ message *m_ptr; /* pointer to message in the caller's space */ return(result); } +/*===========================================================================* + * deadlock * + *===========================================================================*/ +PRIVATE int deadlock(function, cp, src_dst) +int function; /* trap number */ +register struct proc *cp; /* pointer to caller */ +register int src_dst; /* src or dst process */ +{ +/* Check for deadlock. This can happen if 'caller_ptr' and 'src_dst' have + * a cyclic dependency of blocking send and receive calls. The only cyclic + * depency that is not fatal is if the caller and target directly SEND(REC) + * and RECEIVE to each other. If a deadlock is found, the group size is + * returned. Otherwise zero is returned. + */ + register struct proc *xp; /* process pointer */ + int group_size = 1; /* start with only caller */ + int trap_flags; + + while (src_dst != ANY) { /* check while process nr */ + xp = proc_addr(src_dst); /* follow chain of processes */ + group_size ++; /* extra process in group */ + + /* Check whether the last process in the chain has a depency. If it + * has not, the cycle cannot be closed and we are done. + */ + if (xp->p_rts_flags & RECEIVING) { /* xp has dependency */ + src_dst = xp->p_getfrom; /* get xp's source */ + } else if (xp->p_rts_flags & SENDING) { /* xp has dependency */ + src_dst = xp->p_sendto; /* get xp's destination */ + } else { + return(0); /* not a deadlock */ + } + + /* Now check if there is a cyclic dependency. For group sizes of two, + * a combination of SEND(REC) and RECEIVE is not fatal. Larger groups + * or other combinations indicate a deadlock. + */ + if (src_dst == proc_nr(cp)) { /* possible deadlock */ + if (group_size == 2) { /* caller and src_dst */ + /* The function number is magically converted to flags. */ + if ((xp->p_rts_flags ^ (function << 2)) & SENDING) { + return(0); /* not a deadlock */ + } + } + return(group_size); /* deadlock found */ + } + } + return(0); /* not a deadlock */ +} + /*===========================================================================* * mini_send * *===========================================================================*/ @@ -209,14 +270,6 @@ unsigned flags; /* system call flags */ */ register struct proc *dst_ptr = proc_addr(dst); register struct proc **xpp; - register struct proc *xp; - - /* Check for deadlock by 'caller_ptr' and 'dst' sending to each other. */ - xp = dst_ptr; - while (xp->p_rts_flags & SENDING) { /* check while sending */ - xp = proc_addr(xp->p_sendto); /* get xp's destination */ - if (xp == caller_ptr) return(ELOCKED); /* deadlock if cyclic */ - } /* Check if 'dst' is blocked waiting for this message. The destination's * SENDING flag may be set when its SENDREC call blocked while sending. diff --git a/kernel/system/do_exit.c b/kernel/system/do_exit.c index 85278adeb..67fb1d18d 100644 --- a/kernel/system/do_exit.c +++ b/kernel/system/do_exit.c @@ -65,7 +65,9 @@ register struct proc *rc; /* slot of process to clean up */ while (*xpp != NIL_PROC) { /* check entire queue */ if (*xpp == rc) { /* process is on the queue */ *xpp = (*xpp)->p_q_link; /* replace by next process */ - break; /* done, can only send one */ + kprintf("Proc %d removed from queue at %d\n", + proc_nr(rc), rc->p_sendto); + break; /* can only be queued once */ } xpp = &(*xpp)->p_q_link; /* proceed to next queued */ } @@ -81,11 +83,13 @@ register struct proc *rc; /* slot of process to clean up */ if ((rp->p_rts_flags & RECEIVING) && rp->p_getfrom == proc_nr(rc)) { rp->p_reg.retreg = EDEADSRCDST; /* report source died */ rp->p_rts_flags &= ~RECEIVING; /* no longer receiving */ + kprintf("Proc %d receive dead src %d\n", proc_nr(rp), proc_nr(rc)); lock_enqueue(rp); /* let process run again */ } else if ((rp->p_rts_flags & SENDING) && rp->p_sendto == proc_nr(rc)) { rp->p_reg.retreg = EDEADSRCDST; /* report destination died */ rp->p_rts_flags &= ~SENDING; /* no longer sending */ + kprintf("Proc %d send dead dst %d\n", proc_nr(rp), proc_nr(rc)); lock_enqueue(rp); /* let process run again */ } } diff --git a/kernel/table.c b/kernel/table.c index 5cfd1bfe1..066ea77df 100755 --- a/kernel/table.c +++ b/kernel/table.c @@ -107,10 +107,7 @@ PUBLIC struct boot_image image[] = { { MEM_PROC_NR, 0, SRV_F, 4, 2, 0, SRV_T, DRV_M, MEM_C, "memory"}, { LOG_PROC_NR, 0, SRV_F, 4, 2, 0, SRV_T, SYS_M, DRV_C, "log" }, { DRVR_PROC_NR, 0, SRV_F, 4, 2, 0, SRV_T, SYS_M, DRV_C, "driver"}, -#if DEAD_CODE - ... WARNING: replace ~0 with USR_T / USR_M -#endif - { INIT_PROC_NR, 0, USR_F, 8, USER_Q, 0, ~0, ~0, 0, "init" }, + { INIT_PROC_NR, 0, USR_F, 8, USER_Q, 0, USR_T, USR_M, 0, "init" }, }; /* Verify the size of the system image table at compile time. Also verify that -- 2.44.0