kernel/fiasco/src/kern/u_semaphore.cpp

   1 INTERFACE:
   2
   3 #include "mapping_tree.h"
   4 #include "kobject.h"
   5 #include "kmem_slab.h"
   6 #include "l4_types.h"
   7 #include "prio_list.h"
   8 #include "thread.h"
   9 #include "slab_cache_anon.h"
  10
  11 class Ram_quota;
  12
  13 class U_semaphore : public Kobject
  14 {
  15   friend class Jdb_semaphore;
  16
  17   FIASCO_DECLARE_KOBJ();
  18
  19 private:
  20   typedef slab_cache_anon Allocator;
  21
  22   Ram_quota *_q;
  23   Locked_prio_list _queue;
  24   bool _valid;
  25 public:
  26   enum Result { Ok, Retry, Timeout, Invalid };
  27
  28 public:
  29   virtual ~U_semaphore();
  30 };
  31
  32
  33 IMPLEMENTATION:
  34
  35 #include "cpu_lock.h"
  36 #include "entry_frame.h"
  37 #include "ipc_timeout.h"
  38 #include "logdefs.h"
  39 #include "mem_space.h"
  40 #include "thread_state.h"
  41 #include "timer.h"
  42
  43 FIASCO_DEFINE_KOBJ(U_semaphore);
  44
  45 PUBLIC /*inline*/
  46 U_semaphore::U_semaphore(Ram_quota *q)
  47   : _q(q), _valid(true)
  48 {}
  49
  50
  51 PRIVATE inline NOEXPORT
  52 void
  53 U_semaphore::set_queued(L4_semaphore *sem, bool q)
  54 {
  55   current()->mem_space()->poke_user(&(sem->flags), (Mword)q);
  56 }
  57
  58
  59 PRIVATE inline NOEXPORT
  60 bool
  61 U_semaphore::pagein_set_queued(Thread *c, L4_semaphore *sem, bool q)
  62 {
  63   jmp_buf pf_recovery;
  64   int err;
  65   if (EXPECT_TRUE ((err = setjmp(pf_recovery)) == 0))
  66     {
  67       c->recover_jmp_buf(&pf_recovery);
  68       // we are preemptible here, in case of a page fault
  69       current()->mem_space()->poke_user(&(sem->flags), (Mword)q);
  70     }
  71
  72   c->recover_jmp_buf(0);
  73   return err == 0;
  74 }
  75
  76
  77 PRIVATE inline NOEXPORT
  78 bool
  79 U_semaphore::add_counter(L4_semaphore *sem, long v)
  80 {
  81   Smword cnt = current()->mem_space()->peek_user(&(sem->counter)) + v;
  82   current()->mem_space()->poke_user(&(sem->counter), cnt);
  83   return cnt;
  84 }
  85
  86
  87 PRIVATE inline NOEXPORT
  88 bool
  89 U_semaphore::valid_semaphore(L4_semaphore *s)
  90 {
  91   if (EXPECT_FALSE(((unsigned long)s & (sizeof(L4_semaphore)-1)) != 0))
  92     return false;
  93
  94   if (EXPECT_FALSE((unsigned long)s >= Mem_layout::User_max))
  95     return false;
  96
  97   return true;
  98 }
  99
 100 PUBLIC
 101 L4_msg_tag
 102 U_semaphore::block_locked(L4_timeout const &to, L4_semaphore *sem, Utcb *u)
 103 {
 104   if (EXPECT_FALSE(!valid_semaphore(sem)))
 105     return L4_msg_tag(0, 0, 0, Invalid);
 106
 107   Thread *c = current_thread();
 108   if (EXPECT_FALSE (!pagein_set_queued(c, sem, true)))
 109     // unhandled page fault semaphore is considered invalid
 110     return L4_msg_tag(0, 0, 0, Invalid);
 111
 112   // *counter is now paged in writable
 113   if (add_counter(sem, 1) > 0)
 114     {
 115       if (!_queue.head())
 116         set_queued(sem, false);
 117
 118       add_counter(sem, -1);
 119       return L4_msg_tag(0, 0, 0, Ok);
 120     }
 121
 122   Unsigned64 t = 0;
 123   if (!to.is_never())
 124     {
 125       t = to.microsecs(Timer::system_clock(), u);
 126       if (!t)
 127         return L4_msg_tag(0, 0, 0, Timeout);
 128     }
 129
 130   c->wait_queue(&_queue);
 131   c->sender_enqueue(&_queue, c->sched_context()->prio());
 132   c->state_change_dirty(~Thread_ready, Thread_send_wait);
 133
 134   IPC_timeout timeout;
 135   if (t)
 136     {
 137       timeout.set(t, c->cpu());
 138       c->set_timeout(&timeout);
 139     }
 140
 141   c->schedule();
 142   // We go here by: (a) a wakeup, (b) a timeout, (c) wait_queue delete,
 143   // (d) ex_regs
 144   c->state_del_dirty(~Thread_ipc_mask);
 145
 146   // The wait_queue was destroyed
 147   if (EXPECT_FALSE(!_valid))
 148     return L4_msg_tag(0, 0, 0, Invalid);
 149
 150   // Two cases:
 151   // 1. c is not in the queue, then the wakeup already occured
 152   // 2. c is in the sender list an the timeout has hit a timeout is flagged
 153   if (EXPECT_FALSE(c->in_sender_list() && timeout.has_hit()))
 154     {
 155       // The timeout really hit so remove c from the queue
 156       c->sender_dequeue(&_queue);
 157       return L4_msg_tag(0, 0, 0, Timeout);
 158     }
 159
 160   return L4_msg_tag(0, 0, 0, Retry);
 161 }
 162
 163
 164 PUBLIC
 165 void
 166 U_semaphore::wakeup_locked(L4_semaphore *sem, bool yield)
 167 {
 168   if (EXPECT_FALSE(!valid_semaphore(sem)))
 169     return;
 170
 171   Thread *c = current_thread();
 172
 173   // basically make queued flag writable
 174   if (EXPECT_FALSE (!pagein_set_queued(c, sem, true)))
 175     // semaphore is invalid
 176     return;
 177
 178   Prio_list_elem *h = _queue.head();
 179   if (!h)
 180     {
 181       set_queued(sem, false); // queue is empty
 182       return;
 183     }
 184
 185   Thread *w = static_cast<Thread*>(Sender::cast(h));
 186   w->sender_dequeue(&_queue);
 187   w->state_change_dirty(~Thread_ipc_mask, Thread_ready);
 188
 189   w->reset_timeout();
 190   w->wait_queue(0);
 191
 192   if (!_queue.head())
 193     set_queued(sem, false); // dequeued the last thread
 194
 195   // XXX: bad hack, need to sync queue
 196   if (w->cpu() != current_cpu())
 197     {
 198       w->activate();
 199       return;
 200     }
 201
 202   if (c->schedule_in_progress())
 203     return;
 204
 205   if (w->sched()->deblock(current_cpu(), current()->sched(), true))
 206     current()->switch_to_locked(w);
 207   else if (yield && w->sched()->prio() == current()->sched()->prio())
 208     {
 209       current()->switch_to_locked(w);
 210 #if 0
 211       w->ready_enqueue();
 212       current()->switch_sched(current()->sched());
 213       current()->schedule();
 214 #endif
 215     }
 216   else
 217     w->ready_enqueue();
 218 }
 219
 220
 221 IMPLEMENT
 222 U_semaphore::~U_semaphore()
 223 {
 224   _valid = false;
 225
 226   while (Prio_list_elem *h = _queue.head())
 227     {
 228       Thread *w = static_cast<Thread*>(Sender::cast(h));
 229       w->sender_dequeue(&_queue);
 230       w->state_change_safely(~Thread_ipc_mask, Thread_ready);
 231       w->ready_enqueue();
 232       w->reset_timeout();
 233     }
 234
 235   Lock_guard<Cpu_lock> guard(&cpu_lock);
 236
 237   current()->schedule();
 238 }
 239
 240 PUBLIC static
 241 U_semaphore*
 242 U_semaphore::alloc(Ram_quota *q)
 243 {
 244   void *nq;
 245   if (q->alloc(sizeof(U_semaphore)) && (nq = allocator()->alloc()))
 246     return new (nq) U_semaphore(q);
 247
 248   return 0;
 249 }
 250
 251 PUBLIC
 252 void *
 253 U_semaphore::operator new (size_t, void *p)
 254 { return p; }
 255
 256 PUBLIC
 257 void
 258 U_semaphore::operator delete (void *_l)
 259 {
 260   U_semaphore *l = reinterpret_cast<U_semaphore*>(_l);
 261   if (l->_q)
 262     l->_q->free(sizeof(U_semaphore));
 263
 264   allocator()->free(l);
 265 }
 266
 267
 268 static Kmem_slab_t<U_semaphore> _usem_allocator("U_semaphore");
 269
 270 PRIVATE static
 271 U_semaphore::Allocator *
 272 U_semaphore::allocator()
 273 { return &_usem_allocator; }
 274
 275
 276 PUBLIC
 277 void
 278 U_semaphore::invoke(L4_obj_ref, Mword, Syscall_frame *f, Utcb *u)
 279 {
 280   //printf ("  do it (%p)\n", l);
 281   LOG_TRACE("User semaphore", "sem", ::current(), __usem_fmt,
 282     Log_entry *le = tbe->payload<Log_entry>();
 283     le->tag = f->tag().raw();
 284     le->id = dbg_id();
 285     le->sem = u->values[0]);
 286
 287   switch (f->tag().proto())
 288     {
 289     case 0: //Sys_u_lock_frame::Sem_sleep:
 290       //LOG_MSG_3VAL(this, "USBLOCK", regs->timeout().raw(), 0, 0);
 291       f->tag(block_locked(f->timeout().rcv, (L4_semaphore*)u->values[0], u));
 292       //LOG_MSG_3VAL(this, "USBLOCK+", res, 0, 0);
 293       return;
 294     case 1: //Sys_u_lock_frame::Sem_wakeup:
 295       //LOG_MSG(this, "USWAKE");
 296       wakeup_locked((L4_semaphore*)u->values[0], true);
 297       f->tag(L4_msg_tag(0,0,0,0));
 298       return;
 299     case 2: //Sys_u_lock_frame::Sem_wakeup:
 300       //LOG_MSG(this, "USWAKE");
 301       wakeup_locked((L4_semaphore*)u->values[0], false);
 302       f->tag(L4_msg_tag(0,0,0,0));
 303       return;
 304     default:
 305       break;
 306     }
 307
 308   f->tag(L4_msg_tag(0,0,0,-L4_err::EInval));
 309 }
 310
 311
 312 // -----------------------------------------------------------------------
 313 INTERFACE [debug]:
 314
 315 EXTENSION class U_semaphore
 316 {
 317 public:
 318   struct Log_entry
 319   {
 320     Mword tag;
 321     Mword id;
 322     Address sem;
 323   };
 324
 325   static unsigned log_fmt(Tb_entry *, int, char *) asm ("__usem_fmt");
 326 ;
 327 };
 328
 329 // -----------------------------------------------------------------------
 330 IMPLEMENTATION [debug]:
 331
 332 IMPLEMENT
 333 unsigned
 334 U_semaphore::log_fmt(Tb_entry *e, int maxlen, char *buf)
 335 {
 336   Log_entry *le = e->payload<Log_entry>();
 337   char const *op;
 338   L4_msg_tag tag(le->tag);
 339
 340   switch (tag.proto())
 341     {
 342     case 0: op = "block"; break;
 343     case 1: op = "signal"; break;
 344     default: op = "invalid"; break;
 345     }
 346   return snprintf(buf, maxlen, "sem=%lx op=%s usem=%lx", le->id,
 347                   op, le->sem);
 348 }
 349
 350
 351
 352 #if 0 // Promela model of the lock
 353 #define MAX_THREADS    4
 354 #define MAX_WQ_ENTRIES MAX_THREADS
 355 #define MAX 1
 356 #define LOOPS 1
 357
 358 #define LOCKED 0
 359 #define RETRY  1
 360 #define ERROR  2
 361
 362 bit thread_state[MAX_THREADS];
 363 hidden byte loops[MAX_THREADS];
 364 unsigned in_critical : 4 = 0;
 365 hidden byte temp;
 366
 367 typedef sem_t
 368 {
 369   short counter;
 370   bit queued;
 371   bit queue[MAX_WQ_ENTRIES];
 372 }
 373
 374 sem_t sem;  /*  maybe move init. to init*/
 375
 376
 377 inline init_globals()
 378 {
 379   d_step
 380   {
 381     temp = 0;
 382     sem.counter = MAX;
 383     do
 384       ::
 385         sem.queue[temp] = 0;
 386         temp++;
 387         if
 388           :: (temp >= MAX_WQ_ENTRIES) -> break;
 389           :: else;
 390         fi
 391     od;
 392   }
 393 }
 394
 395 inline enqueue_thread(t)
 396 {
 397   sem.queue[t] = 1;
 398 }
 399
 400 inline dequeue_thread(t)
 401 {
 402   sem.queue[t] = 0;
 403 }
 404
 405 inline queue_head(head)
 406 {
 407   local_temp = 0;
 408   do
 409     ::
 410       if
 411         :: (sem.queue[local_temp]) -> head = local_temp; break;
 412         :: else;
 413       fi;
 414       local_temp++;
 415       if
 416         :: (local_temp >= MAX_WQ_ENTRIES) -> head = local_temp; break;
 417         :: else;
 418       fi;
 419   od
 420 }
 421
 422 inline block(ret, thread)
 423 {
 424   do ::
 425   atomic
 426   {
 427     sem.counter++;
 428     if
 429       :: (sem.counter > 0) -> sem.counter--; ret = LOCKED; break;
 430       :: else
 431     fi;
 432
 433     sem.queued = 1;
 434     enqueue_thread(thread);
 435     thread_state[thread] = 0;
 436
 437     if
 438       :: (thread_state[thread] == 1) -> skip
 439     fi;
 440
 441     if
 442       :: (sem.queue[thread] == 0) -> ret = RETRY; break;
 443       :: else;
 444     fi;
 445
 446     dequeue_thread(thread);
 447     ret = ERROR;
 448     break;
 449   }
 450   od
 451 }
 452
 453 inline wakeup()
 454 {
 455   do ::
 456   atomic
 457   {
 458     queue_head(pf);
 459     if
 460       :: (pf == MAX_THREADS) -> sem.queued = 0; break;
 461       :: else;
 462     fi;
 463
 464     dequeue_thread(pf);
 465     thread_state[pf] = 1;
 466     queue_head(pf);
 467     if :: (pf == MAX_THREADS) -> sem.queued = 0;
 468        :: else;
 469     fi;
 470     break;
 471   }
 472   od
 473 }
 474
 475 inline down(ret)
 476 {
 477   do
 478     ::
 479       atomic
 480       {
 481         sem.counter--;
 482         if
 483           :: (sem.counter >= 0) -> break;
 484           :: else;
 485         fi
 486       }
 487
 488       block(ret, thread);
 489
 490       if
 491         :: (ret == LOCKED || ret == ERROR) -> break;
 492         :: (ret == RETRY);
 493         :: else assert(false);
 494       fi
 495   od
 496 }
 497
 498
 499 inline up()
 500 {
 501   do
 502     ::
 503       sem.counter++;
 504       if
 505         :: (!sem.queued) -> break;
 506         :: else;
 507       fi;
 508
 509       wakeup();
 510       break;
 511   od
 512 }
 513
 514
 515 proctype Killer()
 516 {
 517   end_k:
 518   do
 519     ::
 520       if
 521         :: (thread_state[0] == 0) -> thread_state[0] = 1;
 522         :: (thread_state[1] == 0) -> thread_state[1] = 1;
 523         :: (thread_state[2] == 0) -> thread_state[2] = 1;
 524       fi
 525   od
 526 }
 527
 528 proctype Thread(byte thread)
 529 {
 530   unsigned pf : 4;
 531   unsigned ret : 4;
 532   unsigned local_temp : 4;
 533
 534 before_down:
 535 L1:  do
 536     ::
 537       down(ret);
 538       if
 539         :: (ret == ERROR) -> goto L1;
 540         :: else;
 541       fi;
 542       atomic {
 543       in_critical++;
 544       assert (in_critical <= MAX);
 545       }
 546
 547 progress1:
 548       in_critical--;
 549       up();
 550
 551       if
 552         :: (loops[thread] == 0) -> break;
 553         :: else;
 554       fi;
 555       loops[thread]--;
 556   od
 557 }
 558
 559 hidden byte threads = 0;
 560 init
 561 {
 562   threads = 0;
 563   in_critical = 0;
 564   init_globals();
 565   run Killer();
 566   do
 567     ::
 568        loops[threads] = LOOPS - 1;
 569        run Thread(threads);
 570        threads++;
 571        if
 572          :: (threads >= MAX_THREADS) -> break;
 573          :: else;
 574        fi
 575   od
 576 }
 577
 578 /*
 579 never
 580 {
 581   do
 582     :: (in_critical == MAX) -> assert(false)
 583     :: else;
 584   od
 585 }
 586 */
 587
 588 #endif