[Kos-cvs] kos/modules/kitc _kmutex.c,1.5,1.6 Makefile,1.6,1.7

[thomas at kos.enix.org]

Update of /home/kos/cvs/kos/modules/kitc
In directory the-doors:/tmp/cvs-serv8985/modules/kitc

Modified Files:
	_kmutex.c Makefile 
Log Message:
2005-01-04  Thomas Petazzoni  <thomas at crazy.kos.nx>

	* modules/test/sem_test.c: Added a test that is similar to the
	mutex one. Instead of using the semaphore as a synchronisation
	primitive, we use it as a mutual exclusion primitive.

	* modules/test/mutex_test.c: Added some usleep() to make sure
	interrupts are generated inside the critical section.

	* modules/kitc/_kmutex.c: doxygen-aware comments.
	(kmutex_lock, kmutex_unlock): Make sure that a mutex that has just
	been released cannot be stolen by an other thread but the one that
	has been woken up. Solution inspired from SOS implementation of
	mutexes.




Index: Makefile
===================================================================
RCS file: /home/kos/cvs/kos/modules/kitc/Makefile,v
retrieving revision 1.6
retrieving revision 1.7
diff -u -d -r1.6 -r1.7
--- Makefile	28 Dec 2004 18:44:36 -0000	1.6
+++ Makefile	4 Jan 2005 21:57:50 -0000	1.7
@@ -1,6 +1,6 @@
 OBJS= kitc.o _ksem.o _kmutex.o _kmsg.o
 
-DEBUG_LEVEL=3
+DEBUG_LEVEL=0
 
 all: kitc.ro
 

Index: _kmutex.c
===================================================================
RCS file: /home/kos/cvs/kos/modules/kitc/_kmutex.c,v
retrieving revision 1.5
retrieving revision 1.6
diff -u -d -r1.5 -r1.6
--- _kmutex.c	29 Dec 2004 19:28:50 -0000	1.5
+++ _kmutex.c	4 Jan 2005 21:57:50 -0000	1.6
@@ -1,16 +1,97 @@
 /*
- * Copyright (C) 2000, David Decotigny, Julien Munier, Thomas Petazzoni
- * http://kos.enix.org
+ * Copyright (C) 2000-2005
+ * David Decotigny, Julien Munier, Thomas Petazzoni
  *
- * Mutex.
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+ * USA.
  *
  * @(#) $Id$
  */
 
+/** @file
+ * Kernel mutex implementation
+ *
+ * @author David Decotigny, Thomas Petazzoni
+ *
+ * <b>What is a mutex ?</b>
+ *
+ * A mutex is a synchronisation primitive useful to provide <i>mutual
+ * exclusion</i>, as its name stands. When a thread owns a mutex, any
+ * other thread that wants the same mutex will be blocked until the
+ * first thread signals that it is done by releasing the mutex.
+ *
+ * The main difference between a mutex and a binary semaphore is the
+ * strong ownership. While a semaphore can be down'ed by a thread and
+ * up'ed by an other thread, a mutex must be released by the same
+ * thread that took it previously.
+ *
+ * We provide two types of mutexes :
+ *
+ * - <b>non-recursive</b> mutexes or <b>regular</b> mutexes. These
+ *   mutexes can only be taken once by the current thread. Before
+ *   taking the same mutex, the current thread must release it.
+ * - <b>recursive</b> mutexes. These mutexes can be taken several
+ *   times by the current thread.
+ *
+ * For example, here is a valid sequence with a recursive mutex but
+ * invalid with non-recursive mutex :
+ *
+ *  -# lock(mutex)
+ *  -# do_something1()
+ *  -# lock(mutex)
+ *  -# do_something2()
+ *  -# unlock(mutex)
+ *  -# do_something3()
+ *  -# unlock(mutex)
+ *
+ * If this sequence is executed with a non-recursive mutex, then the
+ * second lock() will fail and return an error.
+ *
+ * <b>The implementation</b>
+ *
+ * Mutexes are defined by <i>struct kmutex</i> structure. They have to
+ * be initialized and destroyed using kmutex_init() and
+ * kmutex_destroy() respectively.
+ *
+ * The locking and unlock functions are kmutex_lock() and kmutex_unlock()
+ * respectively. kmutex_trylock() is a variant of the kmutex_lock()
+ * function that returns an error if the mutex is not available
+ * instead of waiting for it to become available.
+ */
+
 #include <kos/types.h>
 #include <kitc/kmutex.h>
 #include <task/task.h>
 
+/** Initializes a mutex.
+ *
+ * This function initializes a mutex usable with the kmutex_lock,
+ * kmutex_trylock() and kmutex_unlock() function. It should be
+ * detroyed using the kmutex_destroy() function.
+ *
+ * @param mutex The mutex to initialize
+ *
+ * @param debug_name A name for the synchq associated with the
+ * mutex. The string is <b>not</b> copied, so it should remain
+ * accessible in memory during the lifetime of the mutex.
+ *
+ * @param is_recursive A boolean that tells whether the mutex is a
+ * recursive or not.
+ *
+ * @return ESUCCESS on success, an error code otherwise
+ */
 result_t kmutex_init(struct kmutex *mutex,
 		     const char *debug_name,
 		     bool_t is_recursive)
@@ -24,7 +105,17 @@
   return synchq_init(& mutex->synchq, debug_name);
 }
 
-
+/** Destroy a mutex
+ *
+ * This function destroys a mutex that was previously initialized
+ * using kmutex_init(). It also makes sure that no thread is in the
+ * waiting list of this mutex.
+ *
+ * @param mutex The mutex to destroy
+ *
+ * @return ESUCCESS on success, -EBUSY if the mutex is still in use,
+ * an other error code otherwise
+ */
 result_t kmutex_destroy(struct kmutex *mutex)
 {
   spinlock_flags_t flags;
@@ -47,7 +138,17 @@
   return result;
 }
 
-
+/** Take a mutex
+ *
+ * This function takes the give mutex or blocks until the mutex
+ * becomes available.
+ *
+ * @param mutex The mutex to take
+ *
+ * @return ESUCCESS on success, -EDEADLK if a deadlock is detected. A
+ * deadlock is detected when a thread already owning a non-recursive
+ * mutex tries to take it again.
+ */
 result_t kmutex_lock(struct kmutex *mutex)
 {
   spinlock_flags_t flags;
@@ -56,19 +157,30 @@
 
   synchq_lock(& mutex->synchq, flags);
 
-  DEBUG_PRINT3("[kmutex_lock] Mutex lock 0x%x, %d++ ...",
-	       (unsigned) mutex, mutex->nested_level);
+  DEBUG_PRINT3("[kmutex_lock] Mutex lock 0x%x, %d++ ... from thread 0x%x\n",
+	       (unsigned) mutex, mutex->nested_level,
+	       (unsigned) get_current_thread());
 
   if(mutex->free)
     {
+      /* Mutex is available, take it */
       ASSERT_FATAL(mutex->nested_level == 0);
       mutex->free  = FALSE;
-      mutex->owner = get_current_thread();
     }
   else
     {
       if(mutex->owner == get_current_thread())
 	{
+	  /* The mutex is not available, and we are the owner of the
+	     mutex. Two cases :
+
+	      1) The mutex is recursive, so it is allowed to take
+                 several times the same mutex without unlocking it.
+
+	      2) The mutex is not recursive, taking the same mutex
+                 several times is forbidden, it's a deadlock, so we
+                 return -EDEADLK.
+	  */
 	  if(mutex->is_recursive)
 	    ASSERT_FATAL(mutex->nested_level > 0);
 	  else
@@ -77,23 +189,28 @@
 			   (unsigned) mutex->owner, mutex->owner->name,
 			   (unsigned) get_current_thread(),
 			   get_current_thread()->name);
-
 	      synchq_unlock(& mutex->synchq, flags);
 	      return -EDEADLK;
 	    }
 	}
       else {
-	DEBUG_PRINT3("Waiting ...");
+	/* The mutex is not available, and we are NOT the owner of the
+	   mutex. So we have to wait for the mutex to become
+	   available */
+	DEBUG_PRINT3("Not granted => Waiting\n");
 	synchq_wait_unsafe(& mutex->synchq, NULL, NULL);
-      }
 
-      if(! mutex->is_recursive)
-	ASSERT_FATAL(mutex->nested_level == 0);
+	/* We have been woken up by the kmutex_unlock function because
+	   the mutex is now available. The 'free' field of the mutex
+	   is still set to FALSE, because kmutex_unlock() let it in
+	   this state in order to "reserve" the mutex for us. */
+	ASSERT_FATAL(mutex->free == FALSE);
 
-      mutex->free  = FALSE;
-      mutex->owner = get_current_thread();
+      }
     }
 
+  /* We are now the owner of thread */
+  mutex->owner = get_current_thread();
   mutex->nested_level++;
 
   DEBUG_PRINT3("Granted ! : %d\n", mutex->nested_level);
@@ -103,9 +220,23 @@
   return ESUCCESS;
 }
 
+/** Try to take a mutex
+ *
+ * This function tries to take the mutex. If the mutex is available,
+ * it is taken and the function return ESUCCESS. If it is not
+ * available, it does not block and returns -EBUSY.
+ *
+ * @param mutex The mutex we should try to take
+ *
+ * @return ESUCCESS if the mutex has been taken, -EDEADLK if a
+ * deadlock is detected, -EAGAIN if the mutex is not available
+ *
+ * @todo Test this function
+ *
+ * @warning This function is untested !
+ */
 result_t kmutex_trylock(struct kmutex *mutex)
 {
-  result_t result = ESUCCESS;
   spinlock_flags_t flags;
 
   ASSERT_RETURN_VAL(mutex != NULL, -EINVAL);
@@ -128,21 +259,40 @@
 	  if(mutex->is_recursive)
 	    {
 	      ASSERT_FATAL(mutex->nested_level > 0);
-	      mutex->nested_level++;
 	    }
 	  else
-	    result = -EDEADLK;
+	    {
+	      synchq_unlock(& mutex->synchq, flags);
+	      return -EDEADLK;
+	    }
 	}
       else
-	result = -EAGAIN;
+	{
+	  synchq_unlock(& mutex->synchq, flags);
+	  return -EAGAIN;
+	}
     }
 
+  mutex->nested_level++;
+
   synchq_unlock(& mutex->synchq, flags);
 
-  return result;
+  return ESUCCESS;
 }
 
-
+/** Release a mutex
+ *
+ * This function release a mutex. The mutex has to be hold by the
+ * calling thread. If an other thread is waiting for this mutex, then
+ * the mutex is reserved for it (not marked as free) and the thread is
+ * woken up.
+ *
+ * @param mutex The thread to release
+ *
+ * @return ESUCCESS if the mutex has been successfully released,
+ * -EINVAL if the mutex is already released, -EPERM if the calling
+ * thread is not the owner of the mutex.
+ */
 result_t kmutex_unlock(struct kmutex *mutex)
 {
   spinlock_flags_t flags;
@@ -151,9 +301,12 @@
 
   synchq_lock(& mutex->synchq, flags);
 
-  DEBUG_PRINT3("[kmutex_unlock] Mutex unlock 0x%x, %d--\n",
-	       (unsigned) mutex, mutex->nested_level);
+  DEBUG_PRINT3("[kmutex_unlock] Mutex unlock 0x%x, %d-- from thread 0x%x\n",
+	       (unsigned) mutex, mutex->nested_level,
+	       (unsigned) get_current_thread());
 
+  /* Make sure the calling thread is not trying to release an
+     already-released mutex */
   if (mutex->free)
     {
       synchq_unlock(& mutex->synchq, flags);
@@ -161,6 +314,10 @@
       return -EINVAL;
     }
 
+  /* Make sure the calling thread is the owner of the mutex. This is a
+     strong property of mutexes : only the thread that has taken the
+     mutex can release it. This is the main difference with
+     semaphores */
   if (mutex->owner != get_current_thread())
     {
       synchq_unlock(& mutex->synchq, flags);
@@ -168,6 +325,8 @@
       return -EPERM;
     }
 
+  /* Of course, if the mutex is held by a thread, nested level cannot
+     be negative or null */
   ASSERT_FATAL(mutex->nested_level > 0);
 
   mutex->nested_level--;
@@ -175,10 +334,27 @@
   if (! mutex->is_recursive)
     ASSERT_FATAL(mutex->nested_level == 0);
 
-  if (mutex->nested_level == 0)
-    mutex->free = TRUE;
+  if(mutex->nested_level == 0)
+    {
+      /* If the mutex is not owned by the current thread anymore, then
+	 make sure the owner is null. */
+      mutex->owner = NULL;
 
-  synchq_wakeup_unsafe(& mutex->synchq, NULL, NULL);
+      /* If no thread is waiting for this mutex, then we can safely
+	 mark it as available */
+      if(synchq_is_empty_unsafe(& mutex->synchq))
+	{
+	  mutex->free  = TRUE;
+	}
+      /* Otherwise wake up one thread from the list. It is important
+	 to notice that the thread is NOT marked as available, so that
+	 any thread that calls kmutex_lock() will be locked, and only
+	 the thread we have woken up will really get the mutex */
+      else
+	{
+	  synchq_wakeup_unsafe(& mutex->synchq, NULL, NULL);
+	}
+    }
 
   synchq_unlock(& mutex->synchq, flags);