Xenomai API  2.6.5
schedqueue.h
1 /*
2  * Copyright (C) 2008 Philippe Gerum <[email protected]>.
3  *
4  * Xenomai is free software; you can redistribute it and/or modify
5  * it under the terms of the GNU General Public License as published
6  * by the Free Software Foundation; either version 2 of the License,
7  * or (at your option) any later version.
8  *
9  * Xenomai is distributed in the hope that it will be useful, but
10  * WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12  * General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with Xenomai; if not, write to the Free Software
16  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
17  * 02111-1307, USA.
18  */
19 
20 #ifndef _XENO_NUCLEUS_SCHEDQUEUE_H
21 #define _XENO_NUCLEUS_SCHEDQUEUE_H
22 
23 #include <nucleus/queue.h>
24 
25 #ifdef CONFIG_XENO_OPT_SCALABLE_SCHED
26 /*
27  * Multi-level priority queue, suitable for handling the runnable
28  * thread queue of a scheduling class with O(1) property. We only
29  * manage a descending queuing order, i.e. highest numbered priorities
30  * come first.
31  */
32 #define XNSCHED_MLQ_LEVELS 264
33 
34 #if BITS_PER_LONG * BITS_PER_LONG < XNSCHED_MLQ_LEVELS
35 #error "Internal bitmap cannot hold so many priority levels"
36 #endif
37 
38 #define __MLQ_LONGS ((XNSCHED_MLQ_LEVELS+BITS_PER_LONG-1)/BITS_PER_LONG)
39 
40 struct xnsched_mlq {
41 
42  int loprio, hiprio, elems;
43  unsigned long himap, lomap[__MLQ_LONGS];
44  struct xnqueue queue[XNSCHED_MLQ_LEVELS];
45 
46 };
47 
48 #undef __MLQ_LONGS
49 
50 void initmlq(struct xnsched_mlq *q, int loprio, int hiprio);
51 
52 void addmlq(struct xnsched_mlq *q,
53  struct xnpholder *holder, int idx, int lifo);
54 
55 void removemlq(struct xnsched_mlq *q, struct xnpholder *holder);
56 
57 struct xnpholder *findmlqh(struct xnsched_mlq *q, int prio);
58 
59 struct xnpholder *getheadmlq(struct xnsched_mlq *q);
60 
61 struct xnpholder *getmlq(struct xnsched_mlq *q);
62 
63 struct xnpholder *nextmlq(struct xnsched_mlq *q,
64  struct xnpholder *h);
65 
66 static inline int countmlq(struct xnsched_mlq *q)
67 {
68  return q->elems;
69 }
70 
71 static inline int emptymlq_p(struct xnsched_mlq *q)
72 {
73  return q->himap == 0;
74 }
75 
76 static inline int indexmlq(struct xnsched_mlq *q, int prio)
77 {
78  XENO_ASSERT(QUEUES,
79  prio >= q->loprio && prio <= q->hiprio,
80  xnpod_fatal("priority level %d is out of range ", prio));
81  /*
82  * BIG FAT WARNING: We need to rescale the priority level to a
83  * 0-based range. We use ffnz() to scan the bitmap which MUST
84  * be based on a bit scan forward op. Therefore, the lower the
85  * index value, the higher the priority (since least
86  * significant bits will be found first when scanning the
87  * bitmaps).
88  */
89  return q->hiprio - prio;
90 }
91 
92 static inline int ffsmlq(struct xnsched_mlq *q)
93 {
94  int hi = ffnz(q->himap);
95  int lo = ffnz(q->lomap[hi]);
96  return hi * BITS_PER_LONG + lo; /* Result is undefined if none set. */
97 }
98 
99 static inline void insertmlql(struct xnsched_mlq *q,
100  struct xnpholder *holder, int prio)
101 {
102  addmlq(q, holder, indexmlq(q, prio), 1);
103 }
104 
105 static inline void insertmlqf(struct xnsched_mlq *q,
106  struct xnpholder *holder, int prio)
107 {
108  addmlq(q, holder, indexmlq(q, prio), 0);
109 }
110 
111 static inline void appendmlq(struct xnsched_mlq *q, struct xnpholder *holder)
112 {
113  addmlq(q, holder, indexmlq(q, q->hiprio), 0);
114 }
115 
116 static inline void prependmlq(struct xnsched_mlq *q, struct xnpholder *holder)
117 {
118  addmlq(q, holder, indexmlq(q, q->loprio), 1);
119 }
120 
121 typedef struct xnsched_mlq xnsched_queue_t;
122 
123 #define sched_initpq initmlq
124 #define sched_emptypq_p emptymlq_p
125 #define sched_insertpql insertmlql
126 #define sched_insertpqf insertmlqf
127 #define sched_appendpq appendmlq
128 #define sched_prependpq prependmlq
129 #define sched_removepq removemlq
130 #define sched_getheadpq getheadmlq
131 #define sched_nextpq nextmlq
132 #define sched_getpq getmlq
133 #define sched_findpqh findmlqh
134 
135 #else /* ! CONFIG_XENO_OPT_SCALABLE_SCHED */
136 
137 typedef xnpqueue_t xnsched_queue_t;
138 
139 #define sched_initpq(q, minp, maxp) initpq(q)
140 #define sched_emptypq_p emptypq_p
141 #define sched_insertpql insertpql
142 #define sched_insertpqf insertpqf
143 #define sched_appendpq appendpq
144 #define sched_prependpq prependpq
145 #define sched_removepq removepq
146 #define sched_getheadpq getheadpq
147 #define sched_nextpq nextpq
148 #define sched_getpq getpq
149 #define sched_findpqh findpqh
150 
151 #endif /* !CONFIG_XENO_OPT_SCALABLE_SCHED */
152 
153 #endif /* !_XENO_NUCLEUS_SCHEDQUEUE_H */