L4Re Operating System Framework
Interface and Usage Documentation
Loading...
Searching...
No Matches
scheduler.h
1/*
2 * Copyright (C) 2024 Kernkonzept GmbH.
3 * Author(s): Jakub Jermar <jakub.jermar@kernkonzept.com>
4 *
5 * License: see LICENSE.spdx (in this directory or the directories above)
6 */
7
8#pragma once
9
10#include <vector>
11
12#include <l4/cxx/unique_ptr>
13#include <l4/re/error_helper>
14#include <l4/sys/cxx/ipc_epiface>
15
16#include <l4/libblock-device/debug.h>
17#include <l4/libblock-device/virtio_client.h>
18
19namespace Block_device {
20
34template <typename DEV>
36{
37protected:
38 using Device_type = DEV;
39 using Client_type = Virtio_client<Device_type>;
40
41private:
42 class Irq_object : public L4::Irqep_t<Irq_object>
43 {
44 public:
45 Irq_object(Scheduler_base *parent) : _parent(parent) {}
46
47 void handle_irq() { _parent->schedule(); }
48
49 private:
50 Scheduler_base *_parent;
51 };
52 Irq_object _irq_handler;
53
54 struct Context
55 {
56 cxx::unique_ptr<Pending_request> pending;
57 Client_type *client;
58
59 bool device_busy;
60 l4_size_t cost;
61
62 Context(Client_type *client) : client(client), device_busy(false), cost(0)
63 {}
64
65 bool same_notification_domain(Client_type const *c) const
66 { return c->notification_domain() == client->notification_domain(); }
67 };
68
69 using Queue_type = std::vector<cxx::unique_ptr<Context>>;
70 using Iterator_type = typename Queue_type::const_iterator;
71
72public:
74 : _irq_handler(this), _registry(registry), _next(_clients.cend())
75 {
76 L4Re::chkcap(registry->register_irq_obj(&_irq_handler),
77 "Registering device notify IRQ object.");
78 }
79
80 virtual ~Scheduler_base()
81 {
82 // We need to explicitly delete the IRQ object created in register_irq_obj()
83 // ourselves. Even though unregister_obj() will unmap the cap, it might stay
84 // alive because it was given out to the client. Hence it might be
85 // dispatched even after unregister_obj() returned!
86 L4::Cap<L4::Task>(L4Re::This_task)
87 ->unmap(_irq_handler.obj_cap().fpage(),
89 _registry->unregister_obj(&_irq_handler);
90 }
91
95 virtual l4_size_t get_weight(Client_type const *) = 0;
96
100 virtual l4_size_t get_cost(Pending_request const &) = 0;
101
102 void add_client(Client_type *client)
103 {
104 Dbg::trace().printf("Adding client %p to request scheduler.\n", client);
105
106 // make sure the client uses the request scheduler's device_notify_irq
107 client->set_device_notify_irq(
108 L4::cap_cast<L4::Irq>(_irq_handler.obj_cap()));
109
110 client->set_client_invalidate_cb([this, client](bool fail_pending) {
111 client_invalidate(client, fail_pending);
112 });
113
114 client->set_client_idle_cb([this, client]() { client_idle(client); });
115
116 _clients.push_back(cxx::make_unique<Context>(client));
117 _next = _clients.cend();
118 }
119
120 void remove_client(Client_type *client)
121 {
122 Dbg::trace().printf("Removing client %p from request scheduler.\n", client);
123 _clients.erase(std::remove_if(_clients.begin(), _clients.end(),
124 [client](cxx::unique_ptr<Context> &c) {
125 return c->client == client;
126 }));
127 _next = _clients.cend();
128 }
129
130 Queue_type const &clients()
131 { return _clients; }
132
133private:
135 void client_invalidate(Client_type *client, bool fail_pending)
136 {
137 for (auto &c : _clients)
138 if (c->client == client)
139 {
140 c->device_busy = false;
141 c->cost = 0;
142 if (c->pending)
143 {
144 if (fail_pending)
145 c->pending->fail_request();
146 c->pending.reset();
147 }
148 }
149 }
150
152 void client_idle(Client_type *client)
153 {
154 bool resched = false;
155 for (auto &c : _clients)
156 if (c->device_busy && c->same_notification_domain(client))
157 {
158 c->device_busy = false;
159 resched = true;
160 }
161
162 if (resched)
163 {
164 // By triggering the scheduler asynchronously we make synchronous
165 // request processing in the device implementation possible. In
166 // any case we need to be careful not to start scheduling the
167 // pending request which is being currently handled.
168 L4::cap_cast<L4::Irq>(this->_irq_handler.obj_cap())->trigger();
169 }
170 }
171
181 bool handle_pending(Context *c)
182 {
183 auto cost = get_cost(*(c->pending));
184
185 if (c->cost + cost > get_weight(c->client))
186 {
187 Dbg::trace().printf("Preempting client %p (cost=%zu+%zu, weight=%zu)\n",
188 c->client, c->cost, cost, get_weight(c->client));
189
190 // Charge client's entire weight to force schedule() to give another
191 // client a chance.
192 c->cost = get_weight(c->client);
193 return true;
194 }
195
196 // Keep the pending request in its place while handling the request.
197 // This helps to make sure that the scheduler will not try to schedule
198 // new requests while handling the pending one.
199 int ret = c->pending->handle_request();
200 if (ret == -L4_EBUSY)
201 {
202 c->device_busy = true;
203 return false;
204 }
205
206 c->cost += cost;
207
208 if (ret < 0)
209 c->pending.reset();
210 else
211 c->pending.release();
212 return true;
213 }
214
231 bool schedule_client(Context *c)
232 {
233 if (c->pending)
234 {
235 if (c->device_busy)
236 {
237 Dbg::trace().printf(
238 "Skipping pending request of client %p (busy).\n", c->client);
239 return false;
240 }
241
242 Dbg::trace().printf("Handling pending request of client %p.\n",
243 c->client);
244 // The client has a pending request, we need to handle it first
245 // before new requests can be processed. If we manage to handle it,
246 // we need to check again in the next round for new requests.
247 return handle_pending(c);
248 }
249
250 if (c->client->check_for_new_requests())
251 {
252 auto req = c->client->get_request();
253 if (req)
254 {
255 Dbg::trace().printf("Scheduling request from client %p.\n",
256 c->client);
257 c->pending = c->client->start_request(cxx::move(req));
258 if (c->pending)
259 {
260 // We processed one new request by turning it into a pending
261 // one and possibly sending it to the device (or not). We
262 // need to recheck only if the request was successfully sent
263 // to the device.
264 return handle_pending(c);
265 }
266 // We processed one new request immediately (e.g. failed
267 // sanity check, runtime error or client state).
268 return true;
269 }
270 }
271
272 return false;
273 }
274
287 void schedule()
288 {
289 if (_clients.empty())
290 return;
291
292 if (_next == _clients.cend())
293 _next = _clients.cbegin();
294
295 (*_next)->cost = 0;
296
297 Iterator_type start(_next);
298 bool recheck = false;
299 for (;;)
300 {
301 bool progress = schedule_client(_next->get());
302 // Move onto the next client only after the current client has depleted
303 // its chances to process its queue or if it didn't make any forward
304 // progress
305 if (!progress || ((*_next)->cost >= get_weight((*_next)->client)))
306 {
307 ++_next;
308 if (_next == _clients.cend())
309 _next = _clients.cbegin();
310 (*_next)->cost = 0;
311 }
312 recheck |= progress;
313 if (_next == start)
314 {
315 if (!recheck)
316 {
317 // already processed all clients and requests, start with
318 // the next client next time
319 ++_next;
320 break;
321 }
322 else
323 recheck = false;
324 }
325 }
326 }
327
328 L4::Registry_iface *_registry;
329 Queue_type _clients;
330 Iterator_type _next;
331};
332
339template <typename DEV>
341{
342 using Scheduler_base<DEV>::Scheduler_base;
343
345 get_weight(typename Scheduler_base<DEV>::Client_type const *) override
346 { return 1; }
347
349 { return 1; }
350};
351
352
353} // name space
Scheduler base class.
Definition scheduler.h:36
virtual l4_size_t get_weight(Client_type const *)=0
Return the weight of the client.
virtual l4_size_t get_cost(Pending_request const &)=0
Return the cost of the pending request.
C++ interface for capabilities.
Definition capability.h:219
Abstract interface for object registries.
Definition ipc_epiface:334
virtual void unregister_obj(L4::Epiface *o, bool unmap=true)=0
Unregister the given object o from the server.
virtual L4::Cap< L4::Irq > register_irq_obj(L4::Epiface *o)=0
Register o as server-side object for asynchronous IRQs.
Error helper.
unsigned int l4_size_t
Unsigned size type.
Definition l4int.h:35
@ L4_EBUSY
Object currently busy, try later.
Definition err.h:53
@ L4_FP_DELETE_OBJ
Flag that indicates that an unmap operation on object capabilities shall try to delete the correspond...
Definition consts.h:209
@ L4_FP_ALL_SPACES
Flag to tell the unmap operation to revoke permissions from all child mappings including the mapping ...
Definition consts.h:198
T chkcap(T &&cap, char const *extra="", long err=-L4_ENOMEM)
Check for valid capability or raise C++ exception.
Definition error_helper:145
Interface for pending requests.
Definition request.h:16
Round Robin scheduler class.
Definition scheduler.h:341
l4_size_t get_cost(Pending_request const &) override
Return the cost of the pending request.
Definition scheduler.h:348
Epiface implementation for interrupt handlers.
Definition ipc_epiface:294