From 29adc36b906ae3be5afc577450136e11c12bc0a0 Mon Sep 17 00:00:00 2001
From: manuel <manuel@mausz.at>
Date: Fri, 11 May 2012 15:07:44 +0200
Subject: fix wrong behavior of cond_wait/cond_signal in donation case. we
 can't pre-sort the waiters list here either. it's the same as with
 sema_up/sema_down

---
 threads/synch.c | 30 ++++++++++++------------------
 1 file changed, 12 insertions(+), 18 deletions(-)

(limited to 'threads/synch.c')

diff --git a/threads/synch.c b/threads/synch.c
index db204f5..d7e5e39 100644
--- a/threads/synch.c
+++ b/threads/synch.c
@@ -34,8 +34,6 @@
 
 static bool lock_priority_cmp_greater(const struct list_elem *a, const struct list_elem *b,
     void *AUX UNUSED);
-static bool semaphore_priority_cmp_greater(const struct list_elem *a, const struct list_elem *b,
-    void *aux UNUSED);
 
 /* Initializes semaphore SEMA to VALUE.  A semaphore is a
    nonnegative integer along with two atomic operators for
@@ -353,16 +351,6 @@ cond_init (struct condition *cond)
   list_init (&cond->waiters);
 }
 
-/* comparison function for our descending ordered condition waiters list. */
-static bool
-semaphore_priority_cmp_greater(const struct list_elem *a, const struct list_elem *b,
-    void *aux UNUSED)
-{
-  const struct semaphore_elem *s1 = list_entry (a, struct semaphore_elem, elem);
-  const struct semaphore_elem *s2 = list_entry (b, struct semaphore_elem, elem);
-  return (s1->thread->priority > s2->thread->priority);
-}
-
 /* Atomically releases LOCK and waits for COND to be signaled by
    some other piece of code.  After COND is signaled, LOCK is
    reacquired before returning.  LOCK must be held before calling
@@ -396,9 +384,9 @@ cond_wait (struct condition *cond, struct lock *lock)
   sema_init (&waiter.semaphore, 0);
   /* set thread of waiter */
   waiter.thread = thread_current ();
-  /* and add condition to our ordered waiters list */
-  list_insert_ordered (&cond->waiters, &waiter.elem,
-      &semaphore_priority_cmp_greater, NULL);
+  /* and add condition to our waiters list. sorting isn't useful here either.
+     see sema_up()/cond_signal() for more details */
+  list_push_back (&cond->waiters, &waiter->elem);
   lock_release (lock);
   sema_down (&waiter.semaphore);
   lock_acquire (lock);
@@ -419,9 +407,15 @@ cond_signal (struct condition *cond, struct lock *lock UNUSED)
   ASSERT (!intr_context ());
   ASSERT (lock_held_by_current_thread (lock));
 
-  if (!list_empty (&cond->waiters)) 
-    sema_up (&list_entry (list_pop_front (&cond->waiters),
-                          struct semaphore_elem, elem)->semaphore);
+  /* we can't sort the list during insertion that easily as the priority of
+     blocked/waiting threads may change due to priority donation.
+     this is the same as with sema_down()/sema_up() */
+  if (!list_empty (&cond->waiters))
+  {
+      list_sort (&cond->waiters, &semaphore_priority_cmp_greater, NULL);
+      sema_up (&list_entry (list_pop_front (&cond->waiters),
+            struct semaphore_elem, elem)->semaphore);
+  }
 }
 
 /* Wakes up all threads, if any, waiting on COND (protected by
-- 
cgit v1.2.3