Subversion Repositories shark

Rev

Rev 3 | 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
 ------------
38 pj 23
 CVS :        $Id: pc.c,v 1.2 2003-01-07 17:07:50 pj Exp $
2 pj 24
 
25
 File:        $File$
38 pj 26
 Revision:    $Revision: 1.2 $
27
 Last update: $Date: 2003-01-07 17:07:50 $
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]);
239
 
240
  if ( ((PC_mutex_t *)m->opt)->nblocked)
241
    return (EBUSY);
242
 
243
  kern_cli();
244
  if (m->opt) {
245
    kern_free(m->opt,sizeof(PC_mutex_t));
246
    m->opt = NULL;
247
  }
248
  kern_sti();
249
 
250
  return 0;
251
}
252
 
253
/* see pi.c for informations on the blocking algorithm used */
254
static int PC_lock(RLEVEL l, mutex_t *m)
255
{
256
  PC_mutex_resource_des *lev = (PC_mutex_resource_des *)(resource_table[l]);
257
  PC_mutex_t *p;
258
 
259
  kern_cli();
260
 
261
  p = (PC_mutex_t *)m->opt;
262
  if (!p)
263
    /* if the mutex is not initialized, return an error! */
264
    return (EINVAL);
265
 
266
  if (p->owner == exec_shadow) {
267
    /* the task already owns the mutex */
268
    kern_sti();
269
    return (EDEADLK);
270
  }
271
 
272
  if (p->ceiling > lev->priority[exec_shadow])
273
    /* see POSIX standard p. 258 */
274
    return (EINVAL);
275
 
276
  while (!PC_accept(lev, lev->priority[exec_shadow])) {
277
    /* the mutex is locked by someone,
278
       or another mutex with greater ceiling is busy,
279
       "block" the task on the busy mutex with the highest ceiling
280
       (pointed by lev->mlist)...*/
281
 
282
    //kern_printf("Blocking on %d, owner=%d, exec_shadow=%d\n",lev->mlist,lev->mlist->owner,exec_shadow);
283
    proc_table[exec_shadow].shadow = lev->mlist->owner;
284
    lev->blocked[exec_shadow] = lev->mlist->firstblocked;
285
    lev->mlist->firstblocked = exec_shadow;
286
    lev->mlist->nblocked++;
287
 
288
    /* ... call the scheduler... */
289
    scheduler();
290
    //kern_printf("schedule: exec=%d, exec_shadow=%d\n",exec,exec_shadow);
291
    kern_context_load(proc_table[exec_shadow].context);
292
 
293
    /* ... and reaquire the cli() before the test... */
294
    kern_cli();
295
  }
296
 
297
  /* the mutex is free, We can lock it! */
298
  lev = (PC_mutex_resource_des *)(resource_table[l]);
299
  lev->nlocked[exec_shadow]++;
300
 
301
  p->owner = exec_shadow;
302
 
303
  PC_insert(lev, p);
304
 
305
  kern_sti();
306
 
307
  return 0;
308
}
309
 
310
static int PC_trylock(RLEVEL l, mutex_t *m)
311
{
312
  PC_mutex_resource_des *lev = (PC_mutex_resource_des *)(resource_table[l]);
313
  PC_mutex_t *p;
314
 
315
  kern_cli();
316
 
317
  p = (PC_mutex_t *)m->opt;
318
  if (!p)
319
    /* if the mutex is not initialized, return an error! */
320
    return (EINVAL);
321
 
322
  if (p->owner == exec_shadow) {
323
    /* the task already owns the mutex */
324
    kern_sti();
325
    return (EDEADLK);
326
  }
327
 
328
  if (p->ceiling < lev->priority[exec_shadow])
329
    /* see POSIX standard p. 258 */
330
    return (EINVAL);
331
 
332
  while (!PC_accept(lev, lev->priority[exec_shadow])) {
333
    /* a task already owns the mutex */
334
    kern_sti();
335
    return (EBUSY);
336
  }
337
 
338
  /* the mutex is free, We can lock it! */
339
  lev = (PC_mutex_resource_des *)(resource_table[l]);
340
  lev->nlocked[exec_shadow]++;
341
 
342
  p->owner = exec_shadow;
343
 
344
  PC_insert(lev, p);
345
 
346
  kern_sti();
347
 
348
  return 0;
349
}
350
 
351
static int PC_unlock(RLEVEL l, mutex_t *m)
352
{
353
  PC_mutex_resource_des *lev;
354
  PC_mutex_t *p;
355
  int i, j;
356
 
357
  p = (PC_mutex_t *)m->opt;
358
  if (!p)
359
    return (EINVAL);
360
 
361
  if (p->owner != exec_shadow) {
362
    /* the mutex is owned by another task!!! */
363
    kern_sti();
364
    return (EPERM);
365
  }
366
 
367
  proc_table[exec_shadow].context = kern_context_save();
368
 
369
  /* the mutex is mine */
370
  lev = (PC_mutex_resource_des *)(resource_table[l]);
371
  lev->nlocked[exec_shadow]--;
372
 
373
  p->owner = NIL;
374
 
375
  /* we unblock all the waiting tasks... */
376
  i = p->firstblocked;
377
  p->firstblocked = NIL;
378
 
379
  while (i != NIL) {
380
    proc_table[i].shadow = j = i;
381
    i = lev->blocked[i];
382
    lev->blocked[j] = NIL;
383
  }
384
  p->nblocked = 0;
385
 
386
  PC_extract(lev, p);
387
 
388
/*  {
389
   int xxx;
390
   kern_printf("(PC_unlock owner=%d ",p->owner);
391
   for (xxx = 0; xxx<5; xxx++) kern_printf("p%d s%d|",xxx, proc_table[xxx].shadow);
392
   kern_printf(")\n");
393
  }*/
394
 
395
  scheduler();
396
  kern_context_load(proc_table[exec_shadow].context);
397
 
398
  return 0;
399
}
400
 
38 pj 401
RLEVEL PC_register_module(void)
2 pj 402
{
403
  RLEVEL l;                  /* the level that we register */
404
  PC_mutex_resource_des *m;  /* for readableness only */
405
  PID i;                     /* a counter */
406
 
407
  printk("PC_register_module\n");
408
 
409
  /* request an entry in the level_table */
410
  l = resource_alloc_descriptor();
411
 
412
  /* alloc the space needed for the EDF_level_des */
413
  m = (PC_mutex_resource_des *)kern_alloc(sizeof(PC_mutex_resource_des));
414
 
415
  /* update the level_table with the new entry */
416
  resource_table[l] = (resource_des *)m;
417
 
418
  /* fill the resource_des descriptor */
419
  m->m.r.rtype                       = MUTEX_RTYPE;
420
  m->m.r.res_register                = PC_res_register;
421
  m->m.r.res_detach                  = PC_res_detach;
422
 
423
  /* fill the mutex_resource_des descriptor */
424
  m->m.init                          = PC_init;
425
  m->m.destroy                       = PC_destroy;
426
  m->m.lock                          = PC_lock;
427
  m->m.trylock                       = PC_trylock;
428
  m->m.unlock                        = PC_unlock;
429
 
430
  /* fill the PC_mutex_resource_des descriptor */
431
  for (i=0; i<MAX_PROC; i++)
432
    m->nlocked[i] = 0, m->priority[i] = MAX_DWORD, m->blocked[i] = NIL;
433
 
434
  m->mlist = NULL;
435
 
38 pj 436
  return l;
437
 
2 pj 438
}
439
 
440
/*+ This function gets the ceiling of a PC mutex, and it have to be called
441
    only by a task that owns the mutex.
442
    Returns -1 if the mutex is not a PC mutex, 0 otherwise +*/
443
int PC_get_mutex_ceiling(const mutex_t *mutex, DWORD *ceiling)
444
{
445
  resource_des *r;
446
 
447
  if (!mutex)
448
    return -1;
449
 
450
  r = resource_table[mutex->mutexlevel];
451
 
452
  if (ceiling)
453
    *ceiling = ((PC_mutex_t *)mutex->opt)->ceiling;
454
  else
455
    return -1;
456
 
457
  return 0;
458
}
459
 
460
/*+ This function sets the ceiling of a PC mutex, and it have to be called
461
    only by a task that owns the mutex.
462
    Returns -1 if the mutex is not a PC mutex, 0 otherwise +*/
463
int PC_set_mutex_ceiling(mutex_t *mutex, DWORD ceiling, DWORD *old_ceiling)
464
{
465
  resource_des *r;
466
 
467
  if (!mutex)
468
    return -1;
469
 
470
  r = resource_table[mutex->mutexlevel];
471
 
472
  if (old_ceiling)
473
    *old_ceiling = ((PC_mutex_t *)mutex->opt)->ceiling;
474
 
475
  ((PC_mutex_t *)mutex->opt)->ceiling = ceiling;
476
  return 0;
477
}
478
 
479
void PC_set_task_ceiling(RLEVEL r, PID p, DWORD priority)
480
{
481
  PC_mutex_resource_des *m = (PC_mutex_resource_des *)(resource_table[r]);
482
  m->priority[p] = priority;
483
}
484