Subversion Repositories shark

Rev

Rev 321 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
2 pj 1
/*
2
 * Project: S.Ha.R.K.
3
 *
4
 * Coordinators:
5
 *   Giorgio Buttazzo    <giorgio@sssup.it>
6
 *   Paolo Gai           <pj@gandalf.sssup.it>
7
 *
8
 * Authors     :
9
 *   Paolo Gai           <pj@gandalf.sssup.it>
10
 *   Massimiliano Giorgi <massy@gandalf.sssup.it>
11
 *   Luca Abeni          <luca@gandalf.sssup.it>
12
 *   (see the web pages for full authors list)
13
 *
14
 * ReTiS Lab (Scuola Superiore S.Anna - Pisa - Italy)
15
 *
16
 * http://www.sssup.it
17
 * http://retis.sssup.it
18
 * http://shark.sssup.it
19
 */
20
 
21
/**
22
 ------------
385 giacomo 23
 CVS :        $Id: pc.c,v 1.7 2004-01-08 20:10:41 giacomo Exp $
2 pj 24
 
25
 File:        $File$
385 giacomo 26
 Revision:    $Revision: 1.7 $
27
 Last update: $Date: 2004-01-08 20:10:41 $
2 pj 28
 ------------
29
 
30
 Priority Ceiling protocol. see pc.h for more details...
31
 
32
**/
33
 
34
/*
35
 * Copyright (C) 2000 Paolo Gai
36
 *
37
 * This program is free software; you can redistribute it and/or modify
38
 * it under the terms of the GNU General Public License as published by
39
 * the Free Software Foundation; either version 2 of the License, or
40
 * (at your option) any later version.
41
 *
42
 * This program is distributed in the hope that it will be useful,
43
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
44
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
45
 * GNU General Public License for more details.
46
 *
47
 * You should have received a copy of the GNU General Public License
48
 * along with this program; if not, write to the Free Software
49
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
50
 *
51
 */
52
 
53
 
54
#include <modules/pc.h>
55
 
56
#include <ll/ll.h>
57
#include <ll/string.h>
58
#include <ll/stdio.h>
59
#include <kernel/const.h>
60
#include <sys/types.h>
61
#include <kernel/var.h>
62
#include <kernel/func.h>
63
 
385 giacomo 64
#include <tracer.h>
65
 
2 pj 66
typedef struct PC_mutexstruct_t PC_mutex_t;
67
 
68
/* The PC resource level descriptor */
69
typedef struct {
70
  mutex_resource_des m;     /*+ the mutex interface +*/
71
 
72
  int nlocked[MAX_PROC];    /*+ how many mutex a task currently locks +*/
73
 
74
  PC_mutex_t *mlist;        /*+ the list of the busy mutexes +*/
75
  DWORD priority[MAX_PROC]; /*+ the PC priority of the tasks in the system +*/
76
 
77
  PID blocked[MAX_PROC];
78
 
79
} PC_mutex_resource_des;
80
 
81
/* this is the structure normally pointed by the opt field in the
82
   mutex_t structure */
83
struct PC_mutexstruct_t {
84
  PID owner;
85
  int nblocked;
86
  PID firstblocked;
87
 
88
  DWORD ceiling;
89
  PC_mutex_t *next;
90
  PC_mutex_t *prev;
91
};
92
 
93
/* This is the test done when a task try to lock a mutex.
94
   It checks if the system ceiling is less than the process priority
95
   It returns 1 if the task can lock the mutex, 0 otherwise */
96
static int PC_accept(PC_mutex_resource_des *lev, DWORD prio)
97
{
98
  PC_mutex_t *l = lev->mlist;
99
 
100
  while (l) {
101
    if (l->owner != exec_shadow)
102
      /* l points to a mutex owned by another task. Its ceiling is the
103
         system ceiling... */
104
      return prio < l->ceiling;
105
 
106
    l = l->next;
107
  }
108
 
109
  /* no busy mutexes other than mine!!! */
110
  return 1;
111
}
112
 
113
/* this function inserts a mutex in the mutex list.
114
   the code is similar to q_insert of queue.c */
115
static void PC_insert(PC_mutex_resource_des *lev, PC_mutex_t * m)
116
{
117
    DWORD prio;
118
    PC_mutex_t *p, *q;
119
 
120
    p = NULL;
121
    q = lev->mlist;
122
    prio = m->ceiling;
123
 
124
    while ((q != NULL) && (prio >= q->ceiling)) {
125
        p = q;
126
        q = q->next;
127
    }
128
 
129
    if (p != NULL)
130
      p->next = m;
131
    else
132
      lev->mlist = m;
133
 
134
    if (q != NULL) q->prev = m;
135
 
136
    m->next = q;
137
    m->prev = p;
138
}
139
 
140
/* this function extracts a mutex in the mutex list.
141
   the code is similar to q_extract of queue.c */
142
static void PC_extract(PC_mutex_resource_des *lev, PC_mutex_t * m)
143
{
144
    PC_mutex_t *p, *q;
145
 
146
    //kern_printf("extract: prev=%d next = %d\n",m->prev, m->next);
147
    p = m->prev;
148
    q = m->next;
149
 
150
    if (p == NULL) lev->mlist = q;
151
    else p->next = m->next;
152
 
153
    if (q != NULL) q->prev = m->prev;
154
}
155
 
156
 
38 pj 157
#if 0
2 pj 158
/*+ print resource protocol statistics...+*/
159
static void PC_resource_status(RLEVEL r)
160
{
161
  PC_mutex_resource_des *m = (PC_mutex_resource_des *)(resource_table[r]);
162
  PID i;
163
 
164
  kern_printf("Resources owned by the tasks:\n");
165
  for (i=0; i<MAX_PROC; i++) {
166
     kern_printf("%-4d", m->nlocked[i]);
167
  }
168
 
169
  kern_printf("\nPC priority of the tasks:\n");
170
  for (i=0; i<MAX_PROC; i++) {
171
     kern_printf("%-4ld", m->priority[i]);
172
  }
173
  // in the future: print the status of the blocked semaphores!
174
 
175
}
38 pj 176
#endif
2 pj 177
 
38 pj 178
static int PC_res_register(RLEVEL l, PID p, RES_MODEL *r)
179
{
180
  PC_mutex_resource_des *m = (PC_mutex_resource_des *)(resource_table[l]);
181
  PC_RES_MODEL *pc;
2 pj 182
 
38 pj 183
  if (r->rclass != PC_RCLASS)
2 pj 184
    return -1;
38 pj 185
  if (r->level && r->level !=l)
186
    return -1;
2 pj 187
 
38 pj 188
  pc = (PC_RES_MODEL *)r;
2 pj 189
 
190
  m->priority[p] = pc->priority;
191
  m->nlocked[p] = 0;
38 pj 192
 
193
  return 0;
2 pj 194
}
195
 
196
static void PC_res_detach(RLEVEL l, PID p)
197
{
198
  PC_mutex_resource_des *m = (PC_mutex_resource_des *)(resource_table[l]);
199
 
200
  if (m->nlocked[p])
201
    kern_raise(XMUTEX_OWNER_KILLED, p);
202
  else
203
    m->nlocked[p] = 0;
204
 
205
  m->priority[p] = MAX_DWORD;
206
}
207
 
208
static int PC_init(RLEVEL l, mutex_t *m, const mutexattr_t *a)
209
{
210
  PC_mutex_t *p;
211
 
38 pj 212
  if (a->mclass != PC_MCLASS)
213
    return -1;
214
 
2 pj 215
  p = (PC_mutex_t *) kern_alloc(sizeof(PC_mutex_t));
216
 
217
  /* control if there is enough memory; no control on init on a
218
     non- destroyed mutex */
219
 
220
  if (!p)
221
    return (ENOMEM);
222
 
223
  p->owner = NIL;
224
  p->nblocked = 0;
225
  p->firstblocked = NIL;
226
 
227
  p->ceiling = ((PC_mutexattr_t *)a)->ceiling;
228
  p->next = 0;
229
 
230
 
231
  m->mutexlevel = l;
232
  m->opt = (void *)p;
233
 
234
  return 0;
235
}
236
 
237
 
238
static int PC_destroy(RLEVEL l, mutex_t *m)
239
{
240
//  PC_mutex_resource_des *lev = (PC_mutex_resource_des *)(resource_table[l]);
317 giacomo 241
  SYS_FLAGS f;
2 pj 242
 
243
  if ( ((PC_mutex_t *)m->opt)->nblocked)
244
    return (EBUSY);
245
 
317 giacomo 246
  f = kern_fsave();
2 pj 247
  if (m->opt) {
248
    kern_free(m->opt,sizeof(PC_mutex_t));
249
    m->opt = NULL;
250
  }
317 giacomo 251
  kern_frestore(f);
2 pj 252
 
253
  return 0;
254
}
255
 
256
/* see pi.c for informations on the blocking algorithm used */
257
static int PC_lock(RLEVEL l, mutex_t *m)
258
{
259
  PC_mutex_resource_des *lev = (PC_mutex_resource_des *)(resource_table[l]);
260
  PC_mutex_t *p;
317 giacomo 261
  SYS_FLAGS f;
2 pj 262
 
317 giacomo 263
  f = kern_fsave();
2 pj 264
 
265
  p = (PC_mutex_t *)m->opt;
228 giacomo 266
  if (!p) {
2 pj 267
    /* if the mutex is not initialized, return an error! */
317 giacomo 268
    kern_frestore(f);
2 pj 269
    return (EINVAL);
228 giacomo 270
  }
2 pj 271
 
272
  if (p->owner == exec_shadow) {
273
    /* the task already owns the mutex */
317 giacomo 274
    kern_frestore(f);
2 pj 275
    return (EDEADLK);
276
  }
277
 
228 giacomo 278
  if (p->ceiling > lev->priority[exec_shadow]) {
2 pj 279
    /* see POSIX standard p. 258 */
317 giacomo 280
    kern_frestore(f);
2 pj 281
    return (EINVAL);
228 giacomo 282
  }
2 pj 283
 
284
  while (!PC_accept(lev, lev->priority[exec_shadow])) {
285
    /* the mutex is locked by someone,
286
       or another mutex with greater ceiling is busy,
287
       "block" the task on the busy mutex with the highest ceiling
288
       (pointed by lev->mlist)...*/
289
 
290
    //kern_printf("Blocking on %d, owner=%d, exec_shadow=%d\n",lev->mlist,lev->mlist->owner,exec_shadow);
291
    proc_table[exec_shadow].shadow = lev->mlist->owner;
292
    lev->blocked[exec_shadow] = lev->mlist->firstblocked;
293
    lev->mlist->firstblocked = exec_shadow;
294
    lev->mlist->nblocked++;
295
 
296
    /* ... call the scheduler... */
297
    scheduler();
298
    //kern_printf("schedule: exec=%d, exec_shadow=%d\n",exec,exec_shadow);
385 giacomo 299
    TRACER_LOGEVENT(FTrace_EVT_inheritance,3,proc_table[exec_shadow].context,proc_table[exec].context);
2 pj 300
    kern_context_load(proc_table[exec_shadow].context);
301
 
302
    /* ... and reaquire the cli() before the test... */
319 giacomo 303
    kern_cli();
2 pj 304
  }
305
 
306
  /* the mutex is free, We can lock it! */
307
  lev = (PC_mutex_resource_des *)(resource_table[l]);
308
  lev->nlocked[exec_shadow]++;
309
 
310
  p->owner = exec_shadow;
311
 
312
  PC_insert(lev, p);
313
 
317 giacomo 314
  kern_frestore(f);
2 pj 315
 
316
  return 0;
317
}
318
 
319
static int PC_trylock(RLEVEL l, mutex_t *m)
320
{
321
  PC_mutex_resource_des *lev = (PC_mutex_resource_des *)(resource_table[l]);
322
  PC_mutex_t *p;
317 giacomo 323
  SYS_FLAGS f;
2 pj 324
 
317 giacomo 325
  f = kern_fsave();
2 pj 326
 
327
  p = (PC_mutex_t *)m->opt;
228 giacomo 328
  if (!p) {
2 pj 329
    /* if the mutex is not initialized, return an error! */
317 giacomo 330
    kern_frestore(f);
2 pj 331
    return (EINVAL);
228 giacomo 332
  }
2 pj 333
 
334
  if (p->owner == exec_shadow) {
335
    /* the task already owns the mutex */
317 giacomo 336
    kern_frestore(f);
2 pj 337
    return (EDEADLK);
338
  }
339
 
228 giacomo 340
  if (p->ceiling < lev->priority[exec_shadow]) {
2 pj 341
    /* see POSIX standard p. 258 */
317 giacomo 342
    kern_frestore(f);
2 pj 343
    return (EINVAL);
228 giacomo 344
  }
2 pj 345
 
346
  while (!PC_accept(lev, lev->priority[exec_shadow])) {
347
    /* a task already owns the mutex */
317 giacomo 348
    kern_frestore(f);
2 pj 349
    return (EBUSY);
350
  }
351
 
352
  /* the mutex is free, We can lock it! */
353
  lev = (PC_mutex_resource_des *)(resource_table[l]);
354
  lev->nlocked[exec_shadow]++;
355
 
356
  p->owner = exec_shadow;
357
 
358
  PC_insert(lev, p);
359
 
317 giacomo 360
  kern_frestore(f);
2 pj 361
 
362
  return 0;
363
}
364
 
365
static int PC_unlock(RLEVEL l, mutex_t *m)
366
{
367
  PC_mutex_resource_des *lev;
368
  PC_mutex_t *p;
369
  int i, j;
370
 
371
  p = (PC_mutex_t *)m->opt;
372
  if (!p)
373
    return (EINVAL);
374
 
375
  if (p->owner != exec_shadow) {
376
    /* the mutex is owned by another task!!! */
321 giacomo 377
    kern_sti();
2 pj 378
    return (EPERM);
379
  }
380
 
381
  proc_table[exec_shadow].context = kern_context_save();
382
 
383
  /* the mutex is mine */
384
  lev = (PC_mutex_resource_des *)(resource_table[l]);
385
  lev->nlocked[exec_shadow]--;
386
 
387
  p->owner = NIL;
388
 
389
  /* we unblock all the waiting tasks... */
390
  i = p->firstblocked;
391
  p->firstblocked = NIL;
392
 
393
  while (i != NIL) {
394
    proc_table[i].shadow = j = i;
395
    i = lev->blocked[i];
396
    lev->blocked[j] = NIL;
397
  }
398
  p->nblocked = 0;
399
 
400
  PC_extract(lev, p);
401
 
402
/*  {
403
   int xxx;
404
   kern_printf("(PC_unlock owner=%d ",p->owner);
405
   for (xxx = 0; xxx<5; xxx++) kern_printf("p%d s%d|",xxx, proc_table[xxx].shadow);
406
   kern_printf(")\n");
407
  }*/
408
 
409
  scheduler();
385 giacomo 410
  TRACER_LOGEVENT(FTrace_EVT_inheritance,3,proc_table[exec_shadow].context,proc_table[exec].context);
2 pj 411
  kern_context_load(proc_table[exec_shadow].context);
412
 
413
  return 0;
414
}
415
 
38 pj 416
RLEVEL PC_register_module(void)
2 pj 417
{
418
  RLEVEL l;                  /* the level that we register */
419
  PC_mutex_resource_des *m;  /* for readableness only */
420
  PID i;                     /* a counter */
421
 
422
  printk("PC_register_module\n");
423
 
424
  /* request an entry in the level_table */
425
  l = resource_alloc_descriptor();
426
 
427
  /* alloc the space needed for the EDF_level_des */
428
  m = (PC_mutex_resource_des *)kern_alloc(sizeof(PC_mutex_resource_des));
429
 
430
  /* update the level_table with the new entry */
431
  resource_table[l] = (resource_des *)m;
432
 
433
  /* fill the resource_des descriptor */
434
  m->m.r.rtype                       = MUTEX_RTYPE;
435
  m->m.r.res_register                = PC_res_register;
436
  m->m.r.res_detach                  = PC_res_detach;
437
 
438
  /* fill the mutex_resource_des descriptor */
439
  m->m.init                          = PC_init;
440
  m->m.destroy                       = PC_destroy;
441
  m->m.lock                          = PC_lock;
442
  m->m.trylock                       = PC_trylock;
443
  m->m.unlock                        = PC_unlock;
444
 
445
  /* fill the PC_mutex_resource_des descriptor */
446
  for (i=0; i<MAX_PROC; i++)
447
    m->nlocked[i] = 0, m->priority[i] = MAX_DWORD, m->blocked[i] = NIL;
448
 
449
  m->mlist = NULL;
450
 
38 pj 451
  return l;
452
 
2 pj 453
}
454
 
455
/*+ This function gets the ceiling of a PC mutex, and it have to be called
456
    only by a task that owns the mutex.
457
    Returns -1 if the mutex is not a PC mutex, 0 otherwise +*/
458
int PC_get_mutex_ceiling(const mutex_t *mutex, DWORD *ceiling)
459
{
460
  resource_des *r;
461
 
462
  if (!mutex)
463
    return -1;
464
 
465
  r = resource_table[mutex->mutexlevel];
466
 
467
  if (ceiling)
468
    *ceiling = ((PC_mutex_t *)mutex->opt)->ceiling;
469
  else
470
    return -1;
471
 
472
  return 0;
473
}
474
 
475
/*+ This function sets the ceiling of a PC mutex, and it have to be called
476
    only by a task that owns the mutex.
477
    Returns -1 if the mutex is not a PC mutex, 0 otherwise +*/
478
int PC_set_mutex_ceiling(mutex_t *mutex, DWORD ceiling, DWORD *old_ceiling)
479
{
480
  resource_des *r;
481
 
482
  if (!mutex)
483
    return -1;
484
 
485
  r = resource_table[mutex->mutexlevel];
486
 
487
  if (old_ceiling)
488
    *old_ceiling = ((PC_mutex_t *)mutex->opt)->ceiling;
489
 
490
  ((PC_mutex_t *)mutex->opt)->ceiling = ceiling;
491
  return 0;
492
}
493
 
494
void PC_set_task_ceiling(RLEVEL r, PID p, DWORD priority)
495
{
496
  PC_mutex_resource_des *m = (PC_mutex_resource_des *)(resource_table[r]);
497
  m->priority[p] = priority;
498
}
499