Subversion Repositories shark

Rev

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