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_ipc_in_progress);
 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
 145   // The wait_queue was destroyed
 146   if (EXPECT_FALSE(!_valid))
 147     return L4_msg_tag(0, 0, 0, Invalid);
 148
 149   // Two cases:
 150   // 1. c is not in the queue, then the wakeup already occured
 151   // 2. c is in the sender list an the timeout has hit a timeout is flagged
 152   if (EXPECT_FALSE(c->in_sender_list() && timeout.has_hit()))
 153     {
 154       // The timeout really hit so remove c from the queue
 155       c->sender_dequeue(&_queue);
 156       return L4_msg_tag(0, 0, 0, Timeout);
 157     }
 158
 159   return L4_msg_tag(0, 0, 0, Retry);
 160 }
 161
 162
 163 PUBLIC
 164 void
 165 U_semaphore::wakeup_locked(L4_semaphore *sem, bool yield)
 166 {
 167   if (EXPECT_FALSE(!valid_semaphore(sem)))
 168     return;
 169
 170   Thread *c = current_thread();
 171
 172   // basically make queued flag writable
 173   if (EXPECT_FALSE (!pagein_set_queued(c, sem, true)))
 174     // semaphore is invalid
 175     return;
 176
 177   Prio_list_elem *h = _queue.head();
 178   if (!h)
 179     {
 180       set_queued(sem, false); // queue is empty
 181       return;
 182     }
 183
 184   Thread *w = static_cast<Thread*>(Sender::cast(h));
 185   w->sender_dequeue(&_queue);
 186   w->state_change_dirty(~Thread_ipc_in_progress, Thread_ready);
 187
 188   w->reset_timeout();
 189   w->wait_queue(0);
 190
 191   if (!_queue.head())
 192     set_queued(sem, false); // dequeued the last thread
 193
 194   // XXX: bad hack, need to sync queue
 195   if (w->cpu() != current_cpu())
 196     {
 197       w->activate();
 198       return;
 199     }
 200
 201   if (c->schedule_in_progress())
 202     return;
 203
 204   if (w->sched()->deblock(current_cpu(), current()->sched(), true))
 205     current()->switch_to_locked(w);
 206   else if (yield && w->sched()->prio() == current()->sched()->prio())
 207     {
 208       current()->switch_to_locked(w);
 209 #if 0
 210       w->ready_enqueue();
 211       current()->switch_sched(current()->sched());
 212       current()->schedule();
 213 #endif
 214     }
 215   else
 216     w->ready_enqueue();
 217 }
 218
 219
 220 IMPLEMENT
 221 U_semaphore::~U_semaphore()
 222 {
 223   _valid = false;
 224
 225   while (Prio_list_elem *h = _queue.head())
 226     {
 227       Thread *w = static_cast<Thread*>(Sender::cast(h));
 228       w->sender_dequeue(&_queue);
 229       w->state_change_safely(~Thread_ipc_in_progress, Thread_ready);
 230       w->ready_enqueue();
 231       w->reset_timeout();
 232     }
 233
 234   Lock_guard<Cpu_lock> guard(&cpu_lock);
 235
 236   current()->schedule();
 237 }
 238
 239 PUBLIC static
 240 U_semaphore*
 241 U_semaphore::alloc(Ram_quota *q)
 242 {
 243   void *nq;
 244   if (q->alloc(sizeof(U_semaphore)) && (nq = allocator()->alloc()))
 245     return new (nq) U_semaphore(q);
 246
 247   return 0;
 248 }
 249
 250 PUBLIC
 251 void *
 252 U_semaphore::operator new (size_t, void *p)
 253 { return p; }
 254
 255 PUBLIC
 256 void
 257 U_semaphore::operator delete (void *_l)
 258 {
 259   U_semaphore *l = reinterpret_cast<U_semaphore*>(_l);
 260   if (l->_q)
 261     l->_q->free(sizeof(U_semaphore));
 262
 263   allocator()->free(l);
 264 }
 265
 266
 267 static Kmem_slab_t<U_semaphore> _usem_allocator("U_semaphore");
 268
 269 PRIVATE static
 270 U_semaphore::Allocator *
 271 U_semaphore::allocator()
 272 { return &_usem_allocator; }
 273
 274
 275 PUBLIC
 276 void
 277 U_semaphore::invoke(L4_obj_ref, Mword, Syscall_frame *f, Utcb *u)
 278 {
 279   //printf ("  do it (%p)\n", l);
 280   LOG_TRACE("User semaphore", "sem", ::current(), __usem_fmt,
 281     Log_entry *le = tbe->payload<Log_entry>();
 282     le->tag = f->tag().raw();
 283     le->id = dbg_id();
 284     le->sem = u->values[0]);
 285
 286   switch (f->tag().proto())
 287     {
 288     case 0: //Sys_u_lock_frame::Sem_sleep:
 289       //LOG_MSG_3VAL(this, "USBLOCK", regs->timeout().raw(), 0, 0);
 290       f->tag(block_locked(f->timeout().rcv, (L4_semaphore*)u->values[0], u));
 291       //LOG_MSG_3VAL(this, "USBLOCK+", res, 0, 0);
 292       return;
 293     case 1: //Sys_u_lock_frame::Sem_wakeup:
 294       //LOG_MSG(this, "USWAKE");
 295       wakeup_locked((L4_semaphore*)u->values[0], true);
 296       f->tag(L4_msg_tag(0,0,0,0));
 297       return;
 298     case 2: //Sys_u_lock_frame::Sem_wakeup:
 299       //LOG_MSG(this, "USWAKE");
 300       wakeup_locked((L4_semaphore*)u->values[0], false);
 301       f->tag(L4_msg_tag(0,0,0,0));
 302       return;
 303     default:
 304       break;
 305     }
 306
 307   f->tag(L4_msg_tag(0,0,0,-L4_err::EInval));
 308 }
 309
 310
 311 // -----------------------------------------------------------------------
 312 INTERFACE [debug]:
 313
 314 EXTENSION class U_semaphore
 315 {
 316 public:
 317   struct Log_entry
 318   {
 319     Mword tag;
 320     Mword id;
 321     Address sem;
 322   };
 323
 324   static unsigned log_fmt(Tb_entry *, int, char *) asm ("__usem_fmt");
 325 ;
 326 };
 327
 328 // -----------------------------------------------------------------------
 329 IMPLEMENTATION [debug]:
 330
 331 IMPLEMENT
 332 unsigned
 333 U_semaphore::log_fmt(Tb_entry *e, int maxlen, char *buf)
 334 {
 335   Log_entry *le = e->payload<Log_entry>();
 336   char const *op;
 337   L4_msg_tag tag(le->tag);
 338
 339   switch (tag.proto())
 340     {
 341     case 0: op = "block"; break;
 342     case 1: op = "signal"; break;
 343     default: op = "invalid"; break;
 344     }
 345   return snprintf(buf, maxlen, "sem=%lx op=%s usem=%lx", le->id,
 346                   op, le->sem);
 347 }
 348
 349
 350
 351 #if 0 // Promela model of the lock
 352 #define MAX_THREADS    4
 353 #define MAX_WQ_ENTRIES MAX_THREADS
 354 #define MAX 1
 355 #define LOOPS 1
 356
 357 #define LOCKED 0
 358 #define RETRY  1
 359 #define ERROR  2
 360
 361 bit thread_state[MAX_THREADS];
 362 hidden byte loops[MAX_THREADS];
 363 unsigned in_critical : 4 = 0;
 364 hidden byte temp;
 365
 366 typedef sem_t
 367 {
 368   short counter;
 369   bit queued;
 370   bit queue[MAX_WQ_ENTRIES];
 371 }
 372
 373 sem_t sem;  /*  maybe move init. to init*/
 374
 375
 376 inline init_globals()
 377 {
 378   d_step
 379   {
 380     temp = 0;
 381     sem.counter = MAX;
 382     do
 383       ::
 384         sem.queue[temp] = 0;
 385         temp++;
 386         if
 387           :: (temp >= MAX_WQ_ENTRIES) -> break;
 388           :: else;
 389         fi
 390     od;
 391   }
 392 }
 393
 394 inline enqueue_thread(t)
 395 {
 396   sem.queue[t] = 1;
 397 }
 398
 399 inline dequeue_thread(t)
 400 {
 401   sem.queue[t] = 0;
 402 }
 403
 404 inline queue_head(head)
 405 {
 406   local_temp = 0;
 407   do
 408     ::
 409       if
 410         :: (sem.queue[local_temp]) -> head = local_temp; break;
 411         :: else;
 412       fi;
 413       local_temp++;
 414       if
 415         :: (local_temp >= MAX_WQ_ENTRIES) -> head = local_temp; break;
 416         :: else;
 417       fi;
 418   od
 419 }
 420
 421 inline block(ret, thread)
 422 {
 423   do ::
 424   atomic
 425   {
 426     sem.counter++;
 427     if
 428       :: (sem.counter > 0) -> sem.counter--; ret = LOCKED; break;
 429       :: else
 430     fi;
 431
 432     sem.queued = 1;
 433     enqueue_thread(thread);
 434     thread_state[thread] = 0;
 435
 436     if
 437       :: (thread_state[thread] == 1) -> skip
 438     fi;
 439
 440     if
 441       :: (sem.queue[thread] == 0) -> ret = RETRY; break;
 442       :: else;
 443     fi;
 444
 445     dequeue_thread(thread);
 446     ret = ERROR;
 447     break;
 448   }
 449   od
 450 }
 451
 452 inline wakeup()
 453 {
 454   do ::
 455   atomic
 456   {
 457     queue_head(pf);
 458     if
 459       :: (pf == MAX_THREADS) -> sem.queued = 0; break;
 460       :: else;
 461     fi;
 462
 463     dequeue_thread(pf);
 464     thread_state[pf] = 1;
 465     queue_head(pf);
 466     if :: (pf == MAX_THREADS) -> sem.queued = 0;
 467        :: else;
 468     fi;
 469     break;
 470   }
 471   od
 472 }
 473
 474 inline down(ret)
 475 {
 476   do
 477     ::
 478       atomic
 479       {
 480         sem.counter--;
 481         if
 482           :: (sem.counter >= 0) -> break;
 483           :: else;
 484         fi
 485       }
 486
 487       block(ret, thread);
 488
 489       if
 490         :: (ret == LOCKED || ret == ERROR) -> break;
 491         :: (ret == RETRY);
 492         :: else assert(false);
 493       fi
 494   od
 495 }
 496
 497
 498 inline up()
 499 {
 500   do
 501     ::
 502       sem.counter++;
 503       if
 504         :: (!sem.queued) -> break;
 505         :: else;
 506       fi;
 507
 508       wakeup();
 509       break;
 510   od
 511 }
 512
 513
 514 proctype Killer()
 515 {
 516   end_k:
 517   do
 518     ::
 519       if
 520         :: (thread_state[0] == 0) -> thread_state[0] = 1;
 521         :: (thread_state[1] == 0) -> thread_state[1] = 1;
 522         :: (thread_state[2] == 0) -> thread_state[2] = 1;
 523       fi
 524   od
 525 }
 526
 527 proctype Thread(byte thread)
 528 {
 529   unsigned pf : 4;
 530   unsigned ret : 4;
 531   unsigned local_temp : 4;
 532
 533 before_down:
 534 L1:  do
 535     ::
 536       down(ret);
 537       if
 538         :: (ret == ERROR) -> goto L1;
 539         :: else;
 540       fi;
 541       atomic {
 542       in_critical++;
 543       assert (in_critical <= MAX);
 544       }
 545
 546 progress1:
 547       in_critical--;
 548       up();
 549
 550       if
 551         :: (loops[thread] == 0) -> break;
 552         :: else;
 553       fi;
 554       loops[thread]--;
 555   od
 556 }
 557
 558 hidden byte threads = 0;
 559 init
 560 {
 561   threads = 0;
 562   in_critical = 0;
 563   init_globals();
 564   run Killer();
 565   do
 566     ::
 567        loops[threads] = LOOPS - 1;
 568        run Thread(threads);
 569        threads++;
 570        if
 571          :: (threads >= MAX_THREADS) -> break;
 572          :: else;
 573        fi
 574   od
 575 }
 576
 577 /*
 578 never
 579 {
 580   do
 581     :: (in_critical == MAX) -> assert(false)
 582     :: else;
 583   od
 584 }
 585 */
 586
 587 #endif