kernel/sem.c

   1 /*
   2 ** Copyright 2001, Travis Geiselbrecht. All rights reserved.
   3 ** Distributed under the terms of the NewOS License.
   4 */
   5 #include <kernel/kernel.h>
   6 #include <kernel/sem.h>
   7 #include <kernel/smp.h>
   8 #include <kernel/int.h>
   9 #include <kernel/timer.h>
  10 #include <kernel/debug.h>
  11 #include <kernel/heap.h>
  12 #include <kernel/thread.h>
  13
  14 #include <boot/stage2.h>
  15
  16 #include <libc/string.h>
  17
  18 static struct sem_entry *sems = NULL;
  19 static region_id sem_region = 0;
  20 static bool sems_active = false;
  21
  22 static sem_id next_sem = 0;
  23
  24 static const char *temp_sem_name = "temp sem";
  25
  26 static int sem_spinlock = 0;
  27 #define GRAB_SEM_LIST_LOCK() acquire_spinlock(&sem_spinlock)
  28 #define RELEASE_SEM_LIST_LOCK() release_spinlock(&sem_spinlock)
  29 #define GRAB_SEM_LOCK(s) acquire_spinlock(&(s).lock)
  30 #define RELEASE_SEM_LOCK(s) release_spinlock(&(s).lock)
  31
  32 // used in functions that may put a bunch of threads in the run q at once
  33 #define READY_THREAD_CACHE_SIZE 16
  34
  35 struct sem_timeout_args {
  36         thread_id blocked_thread;
  37         sem_id blocked_sem_id;
  38         int sem_count;
  39 };
  40
  41 void dump_sem_list(int argc, char **argv)
  42 {
  43         int i;
  44
  45         for(i=0; i<MAX_SEMS; i++) {
  46                 if(sems[i].id >= 0) {
  47                         dprintf("0x%x\tid: 0x%x\t\tname: '%s'\n", &sems[i], sems[i].id, sems[i].name);
  48                 }
  49         }
  50 }
  51
  52 static void _dump_sem_info(struct sem_entry *sem)
  53 {
  54         dprintf("SEM:   0x%x\n", sem);
  55         dprintf("name:  '%s'\n", sem->name);
  56         dprintf("count: 0x%x\n", sem->count);
  57         dprintf("queue: head 0x%x tail 0x%x\n", sem->q.head, sem->q.tail);
  58 }
  59
  60 static void dump_sem_info(int argc, char **argv)
  61 {
  62         int i;
  63
  64         if(argc < 2) {
  65                 dprintf("sem: not enough arguments\n");
  66                 return;
  67         }
  68
  69         // if the argument looks like a hex number, treat it as such
  70         if(strlen(argv[1]) > 2 && argv[1][0] == '0' && argv[1][1] == 'x') {
  71                 unsigned long num = atoul(argv[1]);
  72
  73                 if(num > KERNEL_BASE && num <= (KERNEL_BASE + (KERNEL_SIZE - 1))) {
  74                         // XXX semi-hack
  75                         _dump_sem_info((struct sem_entry *)num);
  76                         return;
  77                 } else {
  78                         int slot = num % MAX_SEMS;
  79                         if(sems[slot].id != (int)num) {
  80                                 dprintf("sem 0x%x doesn't exist!\n", num);
  81                                 return;
  82                         }
  83                         _dump_sem_info(&sems[slot]);
  84                         return;
  85                 }
  86         }
  87
  88         // walk through the sem list, trying to match name
  89         for(i=0; i<MAX_SEMS; i++) {
  90                 if(strcmp(argv[1], sems[i].name) == 0) {
  91                         _dump_sem_info(&sems[i]);
  92                         return;
  93                 }
  94         }
  95 }
  96
  97 int sem_init(kernel_args *ka)
  98 {
  99         int i;
 100
 101         dprintf("sem_init: entry\n");
 102
 103         // create and initialize semaphore table
 104         sem_region = vm_create_anonymous_region(vm_get_kernel_aspace_id(), "sem_table", (void **)&sems,
 105                 REGION_ADDR_ANY_ADDRESS, sizeof(struct sem_entry) * MAX_SEMS, REGION_WIRING_WIRED, LOCK_RW|LOCK_KERNEL);
 106         if(sem_region < 0) {
 107                 panic("unable to allocate semaphore table!\n");
 108         }
 109
 110         dprintf("memsetting len %d @ 0x%x\n", sizeof(struct sem_entry) * MAX_SEMS, sems);
 111         memset(sems, 0, sizeof(struct sem_entry) * MAX_SEMS);
 112         dprintf("done\n");
 113         for(i=0; i<MAX_SEMS; i++)
 114                 sems[i].id = -1;
 115
 116         sems_active = true;
 117
 118         // add debugger commands
 119         dbg_add_command(&dump_sem_list, "sems", "Dump a list of all active semaphores");
 120         dbg_add_command(&dump_sem_info, "sem", "Dump info about a particular semaphore");
 121
 122         dprintf("sem_init: exit\n");
 123
 124         return 0;
 125 }
 126
 127 sem_id sem_create(int count, const char *name)
 128 {
 129         int i;
 130         int state;
 131         sem_id retval = -1;
 132         char *temp_name;
 133
 134         if(sems_active == false)
 135                 return -1;
 136
 137         temp_name = (char *)kmalloc(strlen(name)+1);
 138         if(temp_name == NULL)
 139                 return -1;
 140         strcpy(temp_name, name);
 141
 142         state = int_disable_interrupts();
 143         GRAB_SEM_LIST_LOCK();
 144
 145         // find the first empty spot
 146         for(i=0; i<MAX_SEMS; i++) {
 147                 if(sems[i].id == -1) {
 148                         // make the sem id be a multiple of the slot it's in
 149                         if(i >= next_sem % MAX_SEMS) {
 150                                 next_sem += i - next_sem % MAX_SEMS;
 151                         } else {
 152                                 next_sem += MAX_SEMS - (next_sem % MAX_SEMS - i);
 153                         }
 154                         sems[i].id = next_sem++;
 155
 156                         sems[i].lock = 0;
 157                         GRAB_SEM_LOCK(sems[i]);
 158                         RELEASE_SEM_LIST_LOCK();
 159
 160                         sems[i].q.tail = NULL;
 161                         sems[i].q.head = NULL;
 162                         sems[i].count = count;
 163                         sems[i].name = temp_name;
 164                         retval = sems[i].id;
 165
 166                         RELEASE_SEM_LOCK(sems[i]);
 167                         break;
 168                 }
 169         }
 170         if(i >= MAX_SEMS)
 171                 RELEASE_SEM_LIST_LOCK();
 172
 173         if(retval < 0) {
 174                 kfree(temp_name);
 175         }
 176
 177         int_restore_interrupts(state);
 178
 179         return retval;
 180 }
 181
 182 int sem_delete(sem_id id)
 183 {
 184         return sem_delete_etc(id, 0);
 185 }
 186
 187 int sem_delete_etc(sem_id id, int return_code)
 188 {
 189         int slot = id % MAX_SEMS;
 190         int state;
 191         int err = 0;
 192         struct thread *t;
 193         int released_threads = 0;
 194         char *old_name;
 195
 196         if(sems_active == false)
 197                 return -1;
 198         if(id < 0)
 199                 return -1;
 200
 201         state = int_disable_interrupts();
 202         GRAB_SEM_LOCK(sems[slot]);
 203
 204         if(sems[slot].id != id) {
 205                 RELEASE_SEM_LOCK(sems[slot]);
 206                 int_restore_interrupts(state);
 207                 dprintf("sem_delete: invalid sem_id %d\n", id);
 208                 return -1;
 209         }
 210
 211         // free any threads waiting for this semaphore
 212         // put them in the runq in batches, to keep the amount of time
 213         // spent with the thread lock held down to a minimum
 214         {
 215                 struct thread *ready_threads[READY_THREAD_CACHE_SIZE];
 216                 int ready_threads_count = 0;
 217
 218                 while((t = thread_dequeue(&sems[slot].q)) != NULL) {
 219                         t->state = THREAD_STATE_READY;
 220                         t->sem_deleted_retcode = return_code;
 221                         t->sem_count = 0;
 222                         ready_threads[ready_threads_count++] = t;
 223                         released_threads++;
 224
 225                         if(ready_threads_count == READY_THREAD_CACHE_SIZE) {
 226                                 // put a batch of em in the runq at once
 227                                 GRAB_THREAD_LOCK();
 228                                 for(; ready_threads_count > 0; ready_threads_count--)
 229                                         thread_enqueue_run_q(ready_threads[ready_threads_count - 1]);
 230                                 RELEASE_THREAD_LOCK();
 231                                 // ready_threads_count is back to 0
 232                         }
 233                 }
 234                 // put any leftovers in the runq
 235                 if(ready_threads_count > 0) {
 236                         GRAB_THREAD_LOCK();
 237                         for(; ready_threads_count > 0; ready_threads_count--)
 238                                 thread_enqueue_run_q(ready_threads[ready_threads_count - 1]);
 239                         RELEASE_THREAD_LOCK();
 240                 }
 241         }
 242         sems[slot].id = -1;
 243         old_name = sems[slot].name;
 244         sems[slot].name = NULL;
 245
 246         RELEASE_SEM_LOCK(sems[slot]);
 247
 248         if(old_name != temp_sem_name)
 249                 kfree(old_name);
 250
 251         if(released_threads > 0) {
 252                 GRAB_THREAD_LOCK();
 253                 thread_resched();
 254                 RELEASE_THREAD_LOCK();
 255         }
 256
 257         int_restore_interrupts(state);
 258
 259         return err;
 260 }
 261
 262 // Called from a timer handler. Wakes up a semaphore
 263 static int sem_timeout(void *data)
 264 {
 265         struct sem_timeout_args *args = (struct sem_timeout_args *)data;
 266         struct thread *t;
 267         int slot;
 268         int state;
 269
 270         t = thread_get_thread_struct(args->blocked_thread);
 271         if(t == NULL)
 272                 return INT_NO_RESCHEDULE;
 273         slot = args->blocked_sem_id % MAX_SEMS;
 274
 275         state = int_disable_interrupts();
 276         GRAB_SEM_LOCK(sems[slot]);
 277
 278 //      dprintf("sem_timeout: called on 0x%x sem %d, tid %d\n", to, to->sem_id, to->thread_id);
 279
 280         if(sems[slot].id != args->blocked_sem_id) {
 281                 // this thread was not waiting on this semaphore
 282                 panic("sem_timeout: thid %d was trying to wait on sem %d which doesn't exist!\n",
 283                         args->blocked_thread, args->blocked_sem_id);
 284         }
 285
 286         t = thread_dequeue_id(&sems[slot].q, t->id);
 287         if(t != NULL) {
 288                 sems[slot].count += args->sem_count;
 289                 t->state = THREAD_STATE_READY;
 290                 GRAB_THREAD_LOCK();
 291                 thread_enqueue_run_q(t);
 292                 RELEASE_THREAD_LOCK();
 293         }
 294
 295         // XXX handle possibly releasing more threads here
 296
 297         RELEASE_SEM_LOCK(sems[slot]);
 298         int_restore_interrupts(state);
 299
 300         return INT_RESCHEDULE;
 301 }
 302
 303 int sem_acquire(sem_id id, int count)
 304 {
 305         return sem_acquire_etc(id, count, 0, 0, NULL);
 306 }
 307
 308 int sem_acquire_etc(sem_id id, int count, int flags, time_t timeout, int *deleted_retcode)
 309 {
 310         int slot = id % MAX_SEMS;
 311         int state;
 312         int err = 0;
 313
 314         if(sems_active == false)
 315                 return -1;
 316
 317         if(id < 0)
 318                 return -1;
 319
 320         if(count <= 0)
 321                 return -1;
 322
 323         state = int_disable_interrupts();
 324         GRAB_SEM_LOCK(sems[slot]);
 325
 326         if(sems[slot].id != id) {
 327                 dprintf("sem_acquire_etc: invalid sem_id %d\n", id);
 328                 err = -1;
 329                 goto err;
 330         }
 331
 332         if(sems[slot].count - count < 0 && (flags & SEM_FLAG_TIMEOUT) != 0 && timeout == 0) {
 333                 // immediate timeout
 334                 err = -1;
 335                 goto err;
 336         }
 337
 338         if((sems[slot].count -= count) < 0) {
 339                 // we need to block
 340                 struct thread *t = thread_get_current_thread();
 341                 struct timer_event timer; // stick it on the heap, since we may be blocking here
 342                 struct sem_timeout_args args;
 343
 344                 t->next_state = THREAD_STATE_WAITING;
 345                 t->sem_count = min(-sems[slot].count, count); // store the count we need to restore upon release
 346                 t->sem_deleted_retcode = 0;
 347                 thread_enqueue(t, &sems[slot].q);
 348
 349                 if((flags & SEM_FLAG_TIMEOUT) != 0) {
 350 //                      dprintf("sem_acquire_etc: setting timeout sem for %d %d usecs, semid %d, tid %d\n",
 351 //                              timeout, sem_id, t->id);
 352                         // set up an event to go off, with the thread struct as the data
 353                         args.blocked_sem_id = id;
 354                         args.blocked_thread = t->id;
 355                         args.sem_count = count;
 356                         timer_setup_timer(&sem_timeout, &args, &timer);
 357                         timer_set_event(timeout, TIMER_MODE_ONESHOT, &timer);
 358                 }
 359
 360                 RELEASE_SEM_LOCK(sems[slot]);
 361                 GRAB_THREAD_LOCK();
 362                 thread_resched();
 363                 RELEASE_THREAD_LOCK();
 364
 365                 if((flags & SEM_FLAG_TIMEOUT) != 0) {
 366                         // cancel the timer event, in case the sem was deleted and a timer in still active
 367                         timer_cancel_event(&timer);
 368                 }
 369
 370                 int_restore_interrupts(state);
 371                 if(deleted_retcode != NULL)
 372                         *deleted_retcode = t->sem_deleted_retcode;
 373                 return 0;
 374         }
 375
 376 err:
 377         RELEASE_SEM_LOCK(sems[slot]);
 378         int_restore_interrupts(state);
 379
 380         return err;
 381 }
 382
 383 int sem_release(sem_id id, int count)
 384 {
 385         return sem_release_etc(id, count, 0);
 386 }
 387
 388 int sem_release_etc(sem_id id, int count, int flags)
 389 {
 390         int slot = id % MAX_SEMS;
 391         int state;
 392         int released_threads = 0;
 393         int err = 0;
 394         struct thread *ready_threads[READY_THREAD_CACHE_SIZE];
 395         int ready_threads_count = 0;
 396
 397         if(sems_active == false)
 398                 return -1;
 399
 400         if(id < 0)
 401                 return -1;
 402
 403         if(count <= 0)
 404                 return -1;
 405
 406         state = int_disable_interrupts();
 407         GRAB_SEM_LOCK(sems[slot]);
 408
 409         if(sems[slot].id != id) {
 410                 dprintf("sem_release_etc: invalid sem_id %d\n", id);
 411                 err = -1;
 412                 goto err;
 413         }
 414
 415         while(count > 0) {
 416                 int delta = count;
 417                 if(sems[slot].count < 0) {
 418                         struct thread *t = thread_lookat_queue(&sems[slot].q);
 419
 420                         delta = min(count, t->sem_count);
 421                         t->sem_count -= delta;
 422                         if(t->sem_count <= 0) {
 423                                 // release this thread
 424                                 t = thread_dequeue(&sems[slot].q);
 425                                 t->state = THREAD_STATE_READY;
 426                                 ready_threads[ready_threads_count++] = t;
 427                                 released_threads++;
 428                                 t->sem_count = 0;
 429                                 t->sem_deleted_retcode = 0;
 430                         }
 431                 }
 432                 if(ready_threads_count == READY_THREAD_CACHE_SIZE) {
 433                         // put a batch of em in the runq a once
 434                         GRAB_THREAD_LOCK();
 435                         for(; ready_threads_count > 0; ready_threads_count--)
 436                                 thread_enqueue_run_q(ready_threads[ready_threads_count - 1]);
 437                         RELEASE_THREAD_LOCK();
 438                         // ready_threads_count is back to 0
 439                 }
 440
 441                 sems[slot].count += delta;
 442                 count -= delta;
 443         }
 444         RELEASE_SEM_LOCK(sems[slot]);
 445         if(released_threads > 0) {
 446                 // put any leftovers in the runq
 447                 GRAB_THREAD_LOCK();
 448                 if(ready_threads_count > 0) {
 449                         for(; ready_threads_count > 0; ready_threads_count--)
 450                                 thread_enqueue_run_q(ready_threads[ready_threads_count - 1]);
 451                 }
 452                 if((flags & SEM_FLAG_NO_RESCHED) == 0) {
 453                         thread_resched();
 454                 }
 455                 RELEASE_THREAD_LOCK();
 456                 goto outnolock;
 457         }
 458
 459 err:
 460         RELEASE_SEM_LOCK(sems[slot]);
 461 outnolock:
 462         int_restore_interrupts(state);
 463
 464         return err;
 465 }
 466