Subversion Repositories shark

Rev

Rev 317 | 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
 ------------
319 giacomo 23
 CVS :        $Id: pc.c,v 1.5 2003-11-05 19:16:38 giacomo Exp $
2 pj 24
 
25
 File:        $File$
319 giacomo 26
 Revision:    $Revision: 1.5 $
27
 Last update: $Date: 2003-11-05 19:16:38 $
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
 
64
typedef struct PC_mutexstruct_t PC_mutex_t;
65
 
66
/* The PC resource level descriptor */
67
typedef struct {
68
  mutex_resource_des m;     /*+ the mutex interface +*/
69
 
70
  int nlocked[MAX_PROC];    /*+ how many mutex a task currently locks +*/
71
 
72
  PC_mutex_t *mlist;        /*+ the list of the busy mutexes +*/
73
  DWORD priority[MAX_PROC]; /*+ the PC priority of the tasks in the system +*/
74
 
75
  PID blocked[MAX_PROC];
76
 
77
} PC_mutex_resource_des;
78
 
79
/* this is the structure normally pointed by the opt field in the
80
   mutex_t structure */
81
struct PC_mutexstruct_t {
82
  PID owner;
83
  int nblocked;
84
  PID firstblocked;
85
 
86
  DWORD ceiling;
87
  PC_mutex_t *next;
88
  PC_mutex_t *prev;
89
};
90
 
91
/* This is the test done when a task try to lock a mutex.
92
   It checks if the system ceiling is less than the process priority
93
   It returns 1 if the task can lock the mutex, 0 otherwise */
94
static int PC_accept(PC_mutex_resource_des *lev, DWORD prio)
95
{
96
  PC_mutex_t *l = lev->mlist;
97
 
98
  while (l) {
99
    if (l->owner != exec_shadow)
100
      /* l points to a mutex owned by another task. Its ceiling is the
101
         system ceiling... */
102
      return prio < l->ceiling;
103
 
104
    l = l->next;
105
  }
106
 
107
  /* no busy mutexes other than mine!!! */
108
  return 1;
109
}
110
 
111
/* this function inserts a mutex in the mutex list.
112
   the code is similar to q_insert of queue.c */
113
static void PC_insert(PC_mutex_resource_des *lev, PC_mutex_t * m)
114
{
115
    DWORD prio;
116
    PC_mutex_t *p, *q;
117
 
118
    p = NULL;
119
    q = lev->mlist;
120
    prio = m->ceiling;
121
 
122
    while ((q != NULL) && (prio >= q->ceiling)) {
123
        p = q;
124
        q = q->next;
125
    }
126
 
127
    if (p != NULL)
128
      p->next = m;
129
    else
130
      lev->mlist = m;
131
 
132
    if (q != NULL) q->prev = m;
133
 
134
    m->next = q;
135
    m->prev = p;
136
}
137
 
138
/* this function extracts a mutex in the mutex list.
139
   the code is similar to q_extract of queue.c */
140
static void PC_extract(PC_mutex_resource_des *lev, PC_mutex_t * m)
141
{
142
    PC_mutex_t *p, *q;
143
 
144
    //kern_printf("extract: prev=%d next = %d\n",m->prev, m->next);
145
    p = m->prev;
146
    q = m->next;
147
 
148
    if (p == NULL) lev->mlist = q;
149
    else p->next = m->next;
150
 
151
    if (q != NULL) q->prev = m->prev;
152
}
153
 
154
 
38 pj 155
#if 0
2 pj 156
/*+ print resource protocol statistics...+*/
157
static void PC_resource_status(RLEVEL r)
158
{
159
  PC_mutex_resource_des *m = (PC_mutex_resource_des *)(resource_table[r]);
160
  PID i;
161
 
162
  kern_printf("Resources owned by the tasks:\n");
163
  for (i=0; i<MAX_PROC; i++) {
164
     kern_printf("%-4d", m->nlocked[i]);
165
  }
166
 
167
  kern_printf("\nPC priority of the tasks:\n");
168
  for (i=0; i<MAX_PROC; i++) {
169
     kern_printf("%-4ld", m->priority[i]);
170
  }
171
  // in the future: print the status of the blocked semaphores!
172
 
173
}
38 pj 174
#endif
2 pj 175
 
38 pj 176
static int PC_res_register(RLEVEL l, PID p, RES_MODEL *r)
177
{
178
  PC_mutex_resource_des *m = (PC_mutex_resource_des *)(resource_table[l]);
179
  PC_RES_MODEL *pc;
2 pj 180
 
38 pj 181
  if (r->rclass != PC_RCLASS)
2 pj 182
    return -1;
38 pj 183
  if (r->level && r->level !=l)
184
    return -1;
2 pj 185
 
38 pj 186
  pc = (PC_RES_MODEL *)r;
2 pj 187
 
188
  m->priority[p] = pc->priority;
189
  m->nlocked[p] = 0;
38 pj 190
 
191
  return 0;
2 pj 192
}
193
 
194
static void PC_res_detach(RLEVEL l, PID p)
195
{
196
  PC_mutex_resource_des *m = (PC_mutex_resource_des *)(resource_table[l]);
197
 
198
  if (m->nlocked[p])
199
    kern_raise(XMUTEX_OWNER_KILLED, p);
200
  else
201
    m->nlocked[p] = 0;
202
 
203
  m->priority[p] = MAX_DWORD;
204
}
205
 
206
static int PC_init(RLEVEL l, mutex_t *m, const mutexattr_t *a)
207
{
208
  PC_mutex_t *p;
209
 
38 pj 210
  if (a->mclass != PC_MCLASS)
211
    return -1;
212
 
2 pj 213
  p = (PC_mutex_t *) kern_alloc(sizeof(PC_mutex_t));
214
 
215
  /* control if there is enough memory; no control on init on a
216
     non- destroyed mutex */
217
 
218
  if (!p)
219
    return (ENOMEM);
220
 
221
  p->owner = NIL;
222
  p->nblocked = 0;
223
  p->firstblocked = NIL;
224
 
225
  p->ceiling = ((PC_mutexattr_t *)a)->ceiling;
226
  p->next = 0;
227
 
228
 
229
  m->mutexlevel = l;
230
  m->opt = (void *)p;
231
 
232
  return 0;
233
}
234
 
235
 
236
static int PC_destroy(RLEVEL l, mutex_t *m)
237
{
238
//  PC_mutex_resource_des *lev = (PC_mutex_resource_des *)(resource_table[l]);
317 giacomo 239
  SYS_FLAGS f;
2 pj 240
 
241
  if ( ((PC_mutex_t *)m->opt)->nblocked)
242
    return (EBUSY);
243
 
317 giacomo 244
  f = kern_fsave();
2 pj 245
  if (m->opt) {
246
    kern_free(m->opt,sizeof(PC_mutex_t));
247
    m->opt = NULL;
248
  }
317 giacomo 249
  kern_frestore(f);
2 pj 250
 
251
  return 0;
252
}
253
 
254
/* see pi.c for informations on the blocking algorithm used */
255
static int PC_lock(RLEVEL l, mutex_t *m)
256
{
257
  PC_mutex_resource_des *lev = (PC_mutex_resource_des *)(resource_table[l]);
258
  PC_mutex_t *p;
317 giacomo 259
  SYS_FLAGS f;
2 pj 260
 
317 giacomo 261
  f = kern_fsave();
2 pj 262
 
263
  p = (PC_mutex_t *)m->opt;
228 giacomo 264
  if (!p) {
2 pj 265
    /* if the mutex is not initialized, return an error! */
317 giacomo 266
    kern_frestore(f);
2 pj 267
    return (EINVAL);
228 giacomo 268
  }
2 pj 269
 
270
  if (p->owner == exec_shadow) {
271
    /* the task already owns the mutex */
317 giacomo 272
    kern_frestore(f);
2 pj 273
    return (EDEADLK);
274
  }
275
 
228 giacomo 276
  if (p->ceiling > lev->priority[exec_shadow]) {
2 pj 277
    /* see POSIX standard p. 258 */
317 giacomo 278
    kern_frestore(f);
2 pj 279
    return (EINVAL);
228 giacomo 280
  }
2 pj 281
 
282
  while (!PC_accept(lev, lev->priority[exec_shadow])) {
283
    /* the mutex is locked by someone,
284
       or another mutex with greater ceiling is busy,
285
       "block" the task on the busy mutex with the highest ceiling
286
       (pointed by lev->mlist)...*/
287
 
288
    //kern_printf("Blocking on %d, owner=%d, exec_shadow=%d\n",lev->mlist,lev->mlist->owner,exec_shadow);
289
    proc_table[exec_shadow].shadow = lev->mlist->owner;
290
    lev->blocked[exec_shadow] = lev->mlist->firstblocked;
291
    lev->mlist->firstblocked = exec_shadow;
292
    lev->mlist->nblocked++;
293
 
294
    /* ... call the scheduler... */
295
    scheduler();
296
    //kern_printf("schedule: exec=%d, exec_shadow=%d\n",exec,exec_shadow);
297
    kern_context_load(proc_table[exec_shadow].context);
298
 
299
    /* ... and reaquire the cli() before the test... */
319 giacomo 300
    kern_cli();
2 pj 301
  }
302
 
303
  /* the mutex is free, We can lock it! */
304
  lev = (PC_mutex_resource_des *)(resource_table[l]);
305
  lev->nlocked[exec_shadow]++;
306
 
307
  p->owner = exec_shadow;
308
 
309
  PC_insert(lev, p);
310
 
317 giacomo 311
  kern_frestore(f);
2 pj 312
 
313
  return 0;
314
}
315
 
316
static int PC_trylock(RLEVEL l, mutex_t *m)
317
{
318
  PC_mutex_resource_des *lev = (PC_mutex_resource_des *)(resource_table[l]);
319
  PC_mutex_t *p;
317 giacomo 320
  SYS_FLAGS f;
2 pj 321
 
317 giacomo 322
  f = kern_fsave();
2 pj 323
 
324
  p = (PC_mutex_t *)m->opt;
228 giacomo 325
  if (!p) {
2 pj 326
    /* if the mutex is not initialized, return an error! */
317 giacomo 327
    kern_frestore(f);
2 pj 328
    return (EINVAL);
228 giacomo 329
  }
2 pj 330
 
331
  if (p->owner == exec_shadow) {
332
    /* the task already owns the mutex */
317 giacomo 333
    kern_frestore(f);
2 pj 334
    return (EDEADLK);
335
  }
336
 
228 giacomo 337
  if (p->ceiling < lev->priority[exec_shadow]) {
2 pj 338
    /* see POSIX standard p. 258 */
317 giacomo 339
    kern_frestore(f);
2 pj 340
    return (EINVAL);
228 giacomo 341
  }
2 pj 342
 
343
  while (!PC_accept(lev, lev->priority[exec_shadow])) {
344
    /* a task already owns the mutex */
317 giacomo 345
    kern_frestore(f);
2 pj 346
    return (EBUSY);
347
  }
348
 
349
  /* the mutex is free, We can lock it! */
350
  lev = (PC_mutex_resource_des *)(resource_table[l]);
351
  lev->nlocked[exec_shadow]++;
352
 
353
  p->owner = exec_shadow;
354
 
355
  PC_insert(lev, p);
356
 
317 giacomo 357
  kern_frestore(f);
2 pj 358
 
359
  return 0;
360
}
361
 
362
static int PC_unlock(RLEVEL l, mutex_t *m)
363
{
364
  PC_mutex_resource_des *lev;
365
  PC_mutex_t *p;
366
  int i, j;
367
 
368
  p = (PC_mutex_t *)m->opt;
369
  if (!p)
370
    return (EINVAL);
371
 
372
  if (p->owner != exec_shadow) {
373
    /* the mutex is owned by another task!!! */
374
    return (EPERM);
375
  }
376
 
377
  proc_table[exec_shadow].context = kern_context_save();
378
 
379
  /* the mutex is mine */
380
  lev = (PC_mutex_resource_des *)(resource_table[l]);
381
  lev->nlocked[exec_shadow]--;
382
 
383
  p->owner = NIL;
384
 
385
  /* we unblock all the waiting tasks... */
386
  i = p->firstblocked;
387
  p->firstblocked = NIL;
388
 
389
  while (i != NIL) {
390
    proc_table[i].shadow = j = i;
391
    i = lev->blocked[i];
392
    lev->blocked[j] = NIL;
393
  }
394
  p->nblocked = 0;
395
 
396
  PC_extract(lev, p);
397
 
398
/*  {
399
   int xxx;
400
   kern_printf("(PC_unlock owner=%d ",p->owner);
401
   for (xxx = 0; xxx<5; xxx++) kern_printf("p%d s%d|",xxx, proc_table[xxx].shadow);
402
   kern_printf(")\n");
403
  }*/
404
 
405
  scheduler();
406
  kern_context_load(proc_table[exec_shadow].context);
407
 
408
  return 0;
409
}
410
 
38 pj 411
RLEVEL PC_register_module(void)
2 pj 412
{
413
  RLEVEL l;                  /* the level that we register */
414
  PC_mutex_resource_des *m;  /* for readableness only */
415
  PID i;                     /* a counter */
416
 
417
  printk("PC_register_module\n");
418
 
419
  /* request an entry in the level_table */
420
  l = resource_alloc_descriptor();
421
 
422
  /* alloc the space needed for the EDF_level_des */
423
  m = (PC_mutex_resource_des *)kern_alloc(sizeof(PC_mutex_resource_des));
424
 
425
  /* update the level_table with the new entry */
426
  resource_table[l] = (resource_des *)m;
427
 
428
  /* fill the resource_des descriptor */
429
  m->m.r.rtype                       = MUTEX_RTYPE;
430
  m->m.r.res_register                = PC_res_register;
431
  m->m.r.res_detach                  = PC_res_detach;
432
 
433
  /* fill the mutex_resource_des descriptor */
434
  m->m.init                          = PC_init;
435
  m->m.destroy                       = PC_destroy;
436
  m->m.lock                          = PC_lock;
437
  m->m.trylock                       = PC_trylock;
438
  m->m.unlock                        = PC_unlock;
439
 
440
  /* fill the PC_mutex_resource_des descriptor */
441
  for (i=0; i<MAX_PROC; i++)
442
    m->nlocked[i] = 0, m->priority[i] = MAX_DWORD, m->blocked[i] = NIL;
443
 
444
  m->mlist = NULL;
445
 
38 pj 446
  return l;
447
 
2 pj 448
}
449
 
450
/*+ This function gets the ceiling of a PC mutex, and it have to be called
451
    only by a task that owns the mutex.
452
    Returns -1 if the mutex is not a PC mutex, 0 otherwise +*/
453
int PC_get_mutex_ceiling(const mutex_t *mutex, DWORD *ceiling)
454
{
455
  resource_des *r;
456
 
457
  if (!mutex)
458
    return -1;
459
 
460
  r = resource_table[mutex->mutexlevel];
461
 
462
  if (ceiling)
463
    *ceiling = ((PC_mutex_t *)mutex->opt)->ceiling;
464
  else
465
    return -1;
466
 
467
  return 0;
468
}
469
 
470
/*+ This function sets the ceiling of a PC mutex, and it have to be called
471
    only by a task that owns the mutex.
472
    Returns -1 if the mutex is not a PC mutex, 0 otherwise +*/
473
int PC_set_mutex_ceiling(mutex_t *mutex, DWORD ceiling, DWORD *old_ceiling)
474
{
475
  resource_des *r;
476
 
477
  if (!mutex)
478
    return -1;
479
 
480
  r = resource_table[mutex->mutexlevel];
481
 
482
  if (old_ceiling)
483
    *old_ceiling = ((PC_mutex_t *)mutex->opt)->ceiling;
484
 
485
  ((PC_mutex_t *)mutex->opt)->ceiling = ceiling;
486
  return 0;
487
}
488
 
489
void PC_set_task_ceiling(RLEVEL r, PID p, DWORD priority)
490
{
491
  PC_mutex_resource_des *m = (PC_mutex_resource_des *)(resource_table[r]);
492
  m->priority[p] = priority;
493
}
494