kmalloc_incref()
[akaros.git] / kern / src / event.c
1 /* Copyright (c) 2011 The Regents of the University of California
2  * Barret Rhoden <brho@cs.berkeley.edu>
3  * See LICENSE for details.
4  *
5  * Kernel utility functions for sending events and notifications (IPIs) to
6  * processes. */
7
8 #include <ucq.h>
9 #include <bitmask.h>
10 #include <event.h>
11 #include <atomic.h>
12 #include <process.h>
13 #include <smp.h>
14 #include <umem.h>
15 #include <stdio.h>
16 #include <assert.h>
17 #include <pmap.h>
18 #include <schedule.h>
19
20 /* Userspace could give us a vcoreid that causes us to compute a vcpd that is
21  * outside procdata.  If we hit UWLIM, then we've gone farther than we should.
22  * We check the vcoreid, instead of the resulting address, to avoid issues like
23  * address wrap-around. */
24 static bool vcoreid_is_safe(uint32_t vcoreid)
25 {
26         /* MAX_NUM_VCORES == MAX_NUM_CPUS (check procinfo/procdata) */
27         return vcoreid < MAX_NUM_CPUS;
28 }
29
30 /* Note these three helpers return the user address of the mbox, not the KVA.
31  * Load current to access this, and it will work for any process. */
32 static struct event_mbox *get_vcpd_mbox_priv(uint32_t vcoreid)
33 {
34         return &__procdata.vcore_preempt_data[vcoreid].ev_mbox_private;
35 }
36
37 static struct event_mbox *get_vcpd_mbox_pub(uint32_t vcoreid)
38 {
39         return &__procdata.vcore_preempt_data[vcoreid].ev_mbox_public;
40 }
41
42 static struct event_mbox *get_vcpd_mbox(uint32_t vcoreid, int ev_flags)
43 {
44         if (ev_flags & EVENT_VCORE_PRIVATE)
45                 return get_vcpd_mbox_priv(vcoreid);
46         else
47                 return get_vcpd_mbox_pub(vcoreid);
48 }
49
50 /* Can we message the vcore?  (Will it check its messages).  Note this checks
51  * procdata via the user pointer. */
52 static bool can_msg_vcore(uint32_t vcoreid)
53 {
54         struct preempt_data *vcpd = &__procdata.vcore_preempt_data[vcoreid];
55         return atomic_read(&vcpd->flags) & VC_CAN_RCV_MSG;
56 }
57
58 /* Says a vcore can be messaged.  Only call this once you are sure this is true
59  * (holding the proc_lock, etc). */
60 static void set_vcore_msgable(uint32_t vcoreid)
61 {
62         struct preempt_data *vcpd = &__procdata.vcore_preempt_data[vcoreid];
63         atomic_or(&vcpd->flags, VC_CAN_RCV_MSG);
64 }
65
66 /* Posts a message to the mbox, subject to flags.  Feel free to send 0 for the
67  * flags if you don't want to give them the option of EVENT_NOMSG (which is what
68  * we do when sending an indirection event).  Make sure that if mbox is a user
69  * pointer, that you've checked it *and* have that processes address space
70  * loaded.  This can get called with a KVA for mbox. */
71 static void post_ev_msg(struct proc *p, struct event_mbox *mbox,
72                         struct event_msg *msg, int ev_flags)
73 {
74         printd("[kernel] Sending event type %d to mbox %p\n", msg->ev_type, mbox);
75         /* Sanity check */
76         assert(p);
77         /* If they just want a bit (NOMSG), just set the bit */
78         if (ev_flags & EVENT_NOMSG) {
79                 SET_BITMASK_BIT_ATOMIC(mbox->ev_bitmap, msg->ev_type);
80                 wmb();
81                 mbox->ev_check_bits = TRUE;
82         } else {
83                 send_ucq_msg(&mbox->ev_msgs, p, msg);
84         }
85 }
86
87 /* Helper: use this when sending a message to a VCPD mbox.  It just posts to the
88  * ev_mbox and sets notif pending.  Note this uses a userspace address for the
89  * VCPD (though not a user's pointer). */
90 static void post_vc_msg(struct proc *p, uint32_t vcoreid,
91                         struct event_mbox *ev_mbox, struct event_msg *ev_msg,
92                         int ev_flags)
93 {
94         struct preempt_data *vcpd = &__procdata.vcore_preempt_data[vcoreid];
95         post_ev_msg(p, ev_mbox, ev_msg, ev_flags);
96         /* Set notif pending so userspace doesn't miss the message while yielding */
97         wmb(); /* Ensure ev_msg write is before notif_pending */
98         /* proc_notify() also sets this, but the ev_q might not have requested an
99          * IPI, so we have to do it here too. */
100         vcpd->notif_pending = TRUE;
101 }
102
103 /* Helper: will IPI / proc_notify if the flags say so.  We also check to make
104  * sure it is mapped (slight optimization) */
105 static void try_notify(struct proc *p, uint32_t vcoreid, int ev_flags)
106 {
107         /* Note this is an unlocked-peek at the vcoremap */
108         if ((ev_flags & EVENT_IPI) && vcore_is_mapped(p, vcoreid))
109                 proc_notify(p, vcoreid);
110 }
111
112 /* Helper: sends the message and an optional IPI to the vcore.  Sends to the
113  * public mbox.  This is meant for spammy messages. */
114 static void spam_vcore(struct proc *p, uint32_t vcoreid,
115                        struct event_msg *ev_msg, int ev_flags)
116 {
117         post_vc_msg(p, vcoreid, get_vcpd_mbox_pub(vcoreid), ev_msg, ev_flags);
118         try_notify(p, vcoreid, ev_flags);
119 }
120
121 /* Attempts to message a vcore that may or may not have VC_CAN_RCV_MSG set.  If
122  * so, we'll post the message and the message will eventually get dealt with
123  * (when the vcore runs or when it is preempte-recovered). */
124 static bool try_spam_vcore(struct proc *p, uint32_t vcoreid,
125                            struct event_msg *ev_msg, int ev_flags)
126 {
127         /* Not sure if we can or not, so check before spamming.  Technically, the
128          * only critical part is that we __alert, then check can_alert. */
129         if (can_msg_vcore(vcoreid)) {
130                 spam_vcore(p, vcoreid, ev_msg, ev_flags);
131                 wrmb(); /* prev write (notif_pending) must come before following reads*/
132                 if (can_msg_vcore(vcoreid))
133                         return TRUE;
134         }
135         return FALSE;
136 }
137
138 /* Helper: will try to message (INDIR/IPI) a list member (lists of vcores).  We
139  * use this on the online and bulk_preempted vcore lists.  If this succeeds in
140  * alerting a vcore on the list, it'll return TRUE.  We need to be careful here,
141  * since we're reading a list that could be concurrently modified.  The
142  * important thing is that we can always fail if we're unsure (such as with
143  * lists being temporarily empty).  The caller will be able to deal with it via
144  * the ultimate fallback. */
145 static bool spam_list_member(struct vcore_tailq *list, struct proc *p,
146                              struct event_msg *ev_msg, int ev_flags)
147 {
148         struct vcore *vc, *vc_first;
149         uint32_t vcoreid;
150         int loops = 0;
151         vc = TAILQ_FIRST(list);
152         /* If the list appears empty, we'll bail out (failing) after the loop. */
153         while (vc) {
154                 vcoreid = vcore2vcoreid(p, vc);
155                 /* post the alert.  Not using the try_spam_vcore() helper since I want
156                  * something more customized for the lists. */
157                 spam_vcore(p, vcoreid, ev_msg, ev_flags);
158                 wrmb(); /* prev write (notif_pending) must come before following reads*/
159                 /* if they are still alertable after we sent the msg, then they'll get
160                  * it before yielding (racing with userspace yield here).  This check is
161                  * not as critical as the next one, but will allow us to alert vcores
162                  * that happen to concurrently be moved from the active to the
163                  * bulk_preempt list. */
164                 if (can_msg_vcore(vcoreid))
165                         return TRUE;
166                 /* As a backup, if they are still the first on the list, then they are
167                  * still going to get the message.  For the online list, proc_yield()
168                  * will return them to userspace (where they will get the message)
169                  * because __alert_vcore() set notif_pending.  For the BP list, they
170                  * will either be turned on later, or have a preempt message sent about
171                  * their demise.
172                  *
173                  * We race on list membership (and not exclusively VC_CAN_RCV_MSG, so
174                  * that when it fails we can get a new vcore to try (or know WHP there
175                  * are none). */
176                 vc_first = TAILQ_FIRST(list);
177                 if (vc == vc_first)
178                         return TRUE;
179                 /* At this point, the list has changed and the vcore we tried yielded,
180                  * so we try the *new* list head.  Track loops for sanity reasons. */
181                 if (loops++ > 10) {
182                         warn("Too many (%d) attempts to find a vcore, failing!", loops);
183                         return FALSE;   /* always safe to fail! */
184                 }
185                 /* Get set up for your attack run! */
186                 vc = vc_first;
187         }
188         return FALSE;
189 }
190
191 /* This makes sure ev_msg is sent to some vcore, preferring vcoreid.
192  *
193  * One of the goals of FALLBACK (and this func) is to allow processes to yield
194  * cores without fear of losing messages.  Even when yielding and getting
195  * preempted, if your message is spammed, it will get to some vcore.  If
196  * MUST_RUN is set, it'll get to a running vcore.  Messages that you send like
197  * this must be able to handle spurious reads, since more than one vcore is
198  * likely to get the message and handle it.
199  *
200  * We try the desired vcore, using VC_CAN_RCV_MSG.  Failing that, we'll search
201  * the online and then the bulk_preempted lists.  These lists serve as a way to
202  * find likely messageable vcores.  spam_list_member() helps us with them,
203  * failing if anything seems to go wrong.  At which point we just lock and try
204  * to deal with things.  In that scenario, we most likely would need to lock
205  * anyway to wake up the process (was WAITING).
206  *
207  * One tricky thing with sending to the bulk_preempt list is that we may want to
208  * send a message about a (bulk) preemption to someone on that list.  This works
209  * since a given vcore that was preempted will be removed from that list before
210  * we try to send_event() (in theory, there isn't code that can send that event
211  * yet).  Someone else will get the event and wake up the preempted vcore. */
212 static void spam_public_msg(struct proc *p, struct event_msg *ev_msg,
213                                                         uint32_t vcoreid, int ev_flags)
214 {
215         struct vcore *vc;
216         /* First, try posting to the desired vcore (so long as we don't have to send
217          * it to a vcore that will run, like we do for preempt messages). */
218         if (!(ev_flags & EVENT_VCORE_MUST_RUN) &&
219            (try_spam_vcore(p, vcoreid, ev_msg, ev_flags)))
220                 return;
221         /* If the process is WAITING, let's just jump to the fallback */
222         if (p->state == PROC_WAITING)
223                 goto ultimate_fallback;
224         /* If we're here, the desired vcore is unreachable, but the process is
225          * probably RUNNING_M (online_vs) or RUNNABLE_M (bulk preempted or recently
226          * woken up), so we'll need to find another vcore. */
227         if (spam_list_member(&p->online_vcs, p, ev_msg, ev_flags))
228                 return;
229         if (spam_list_member(&p->bulk_preempted_vcs, p, ev_msg, ev_flags))
230                 return;
231         /* Last chance, let's check the head of the inactives.  It might be
232          * alertable (the kernel set it earlier due to an event, or it was a
233          * bulk_preempt that didn't restart), and we can avoid grabbing the
234          * proc_lock. */
235         vc = TAILQ_FIRST(&p->inactive_vcs);
236         if (vc) {       /* might be none in rare circumstances */
237                 if (try_spam_vcore(p, vcore2vcoreid(p, vc), ev_msg, ev_flags)) {
238                         /* Need to ensure the proc wakes up, but only if it was WAITING.
239                          * One way for this to happen is if a normal vcore was preempted
240                          * right as another vcore was yielding, and the preempted
241                          * message was sent after the last vcore yielded (which caused
242                          * us to be WAITING */
243                         if (p->state == PROC_WAITING)
244                                 proc_wakeup(p); /* internally, this double-checks WAITING */
245                         return;
246                 }
247         }
248 ultimate_fallback:
249         /* At this point, we can't find one.  This could be due to a (hopefully
250          * rare) weird yield/request storm, or more commonly because the lists were
251          * empty and the process is simply WAITING (yielded all of its vcores and is
252          * waiting on an event).  Time for the ultimate fallback: locking.  Note
253          * that when we __alert_vcore(), there is a chance we need to mmap, which
254          * grabs the vmr_lock and pte_lock. */
255         spin_lock(&p->proc_lock);
256         if (p->state != PROC_WAITING) {
257                 /* We need to check the online and bulk_preempt lists again, now that we are
258                  * sure no one is messing with them.  If we're WAITING, we can skip
259                  * these (or assert they are empty!). */
260                 vc = TAILQ_FIRST(&p->online_vcs);
261                 if (vc) {
262                         /* there's an online vcore, so just alert it (we know it isn't going
263                          * anywhere), and return */
264                         spam_vcore(p, vcore2vcoreid(p, vc), ev_msg, ev_flags);
265                         spin_unlock(&p->proc_lock);
266                         return;
267                 }
268                 vc = TAILQ_FIRST(&p->bulk_preempted_vcs);
269                 if (vc) {
270                         /* the process is bulk preempted, similar deal to above */
271                         spam_vcore(p, vcore2vcoreid(p, vc), ev_msg, ev_flags);
272                         spin_unlock(&p->proc_lock);
273                         return;
274                 }
275         }
276         /* At this point, we're sure all vcores are yielded, though we might not be
277          * WAITING.  Post to the first on the inactive list (which is the one that
278          * will definitely be woken up) */
279         vc = TAILQ_FIRST(&p->inactive_vcs);
280         assert(vc);
281         spam_vcore(p, vcore2vcoreid(p, vc), ev_msg, ev_flags);
282         /* Set the vcore's alertable flag, to short circuit our last ditch effort
283          * above */
284         set_vcore_msgable(vcore2vcoreid(p, vc));
285         /* The first event to catch the process with no online/bp vcores will need
286          * to wake it up.  (We could be RUNNABLE_M here if another event already woke
287          * us.) and we didn't get lucky with the penultimate fallback.
288          * proc_wakeup (and __proc_wakeup()) will check for WAITING. */
289         spin_unlock(&p->proc_lock);
290         proc_wakeup(p);
291         return;
292 }
293
294 /* Helper: sends an indirection event for an ev_q, preferring vcoreid */
295 static void send_indir(struct proc *p, struct event_queue *ev_q,
296                        uint32_t vcoreid)
297 {
298         struct event_msg local_msg = {0};
299         /* If an alert is already pending and they don't want repeats, just return.
300          * One of the few uses of NOTHROTTLE will be for preempt_msg ev_qs.  Ex: an
301          * INDIR was already sent to the preempted vcore, then alert throttling
302          * would stop another vcore from getting the message about the original
303          * vcore. */
304         if (!(ev_q->ev_flags & EVENT_NOTHROTTLE) && (ev_q->ev_alert_pending))
305                 return;
306         /* We'll eventually get an INDIR through, so don't send any more til
307          * userspace toggles this.  Regardless of other writers to this flag, we
308          * eventually send an alert that causes userspace to turn throttling off
309          * again (before handling all of the ev_q's events).
310          *
311          * This will also squelch IPIs, since there's no reason to send the IPI if
312          * the INDIR is still un-acknowledged.  The vcore is either in vcore
313          * context, attempting to deal with the INDIR, or offline.  This statement
314          * is probably true. */
315         ev_q->ev_alert_pending = TRUE;
316         wmb();  /* force this write to happen before any event writes */
317         local_msg.ev_type = EV_EVENT;
318         local_msg.ev_arg3 = ev_q;
319         /* Don't care about FALLBACK, just send and be done with it.  TODO:
320          * considering getting rid of FALLBACK as an option and making it mandatory
321          * when you want an INDIR.  Having trouble thinking of when you'd want an
322          * INDIR but not a FALLBACK. */
323         if (!(ev_q->ev_flags & EVENT_FALLBACK)) {
324                 printk("[kernel] INDIR requested without FALLBACK, prob a bug.\n");
325                 spam_vcore(p, vcoreid, &local_msg, ev_q->ev_flags);
326                 return;
327         }
328         /* At this point, we actually want to send an INDIR (with FALLBACK).
329          * This will guarantee the message makes it to some vcore.  For flags, we
330          * only want to send flags relevant to spamming messages. */
331         spam_public_msg(p, &local_msg, vcoreid, ev_q->ev_flags & EVENT_SPAM_FLAGS);
332 }
333
334 /* Send an event to ev_q, based on the parameters in ev_q's flag.  We don't
335  * accept null ev_qs, since the caller ought to be checking before bothering to
336  * make a msg and send it to the event_q.  Vcoreid is who the kernel thinks the
337  * message ought to go to (for IPIs).  Appropriate for things like
338  * EV_PREEMPT_PENDING, where we tell the affected vcore.  To have the message go
339  * where the kernel suggests, set EVENT_VCORE_APPRO(priate). */
340 void send_event(struct proc *p, struct event_queue *ev_q, struct event_msg *msg,
341                 uint32_t vcoreid)
342 {
343         struct proc *old_proc;
344         struct event_mbox *ev_mbox = 0;
345         assert(!in_irq_ctx(&per_cpu_info[core_id()]));
346         assert(p);
347         if (p->state == PROC_DYING)
348                 return;
349         printd("[kernel] sending msg to proc %p, ev_q %p\n", p, ev_q);
350         if (!ev_q) {
351                 warn("[kernel] Null ev_q - kernel code should check before sending!");
352                 return;
353         }
354         if (!is_user_rwaddr(ev_q, sizeof(struct event_queue))) {
355                 /* Ought to kill them, just warn for now */
356                 printk("[kernel] Illegal addr for ev_q\n");
357                 return;
358         }
359         /* This should be caught by "future technology" that can tell when the
360          * kernel PFs on the user's behalf.  For now, we catch common userspace bugs
361          * (had this happen a few times). */
362         if (!PTE_ADDR(ev_q)) {
363                 printk("[kernel] Bad addr %p for ev_q\n", ev_q);
364                 return;
365         }
366         /* ev_q is a user pointer, so we need to make sure we're in the right
367          * address space */
368         old_proc = switch_to(p);
369         /* If we're an _S, just spam vcore0, and wake up if necessary. */
370         if (!__proc_is_mcp(p)) {
371                 spam_vcore(p, 0, msg, ev_q->ev_flags);
372                 wrmb(); /* don't let the notif_pending write pass the state read */
373                 /* using the same pattern as in spam_public (which can have multiple
374                  * unblock callbacks */
375                 if (p->state == PROC_WAITING)
376                         proc_wakeup(p);
377                 goto out;
378         }
379         /* Get the vcoreid that we'll message (if appropriate).  For INDIR and
380          * SPAMMING, this is the first choice of a vcore, but other vcores might get
381          * it.  Common case is !APPRO and !ROUNDROBIN.  Note we are clobbering the
382          * vcoreid parameter. */
383         if (!(ev_q->ev_flags & EVENT_VCORE_APPRO))
384                 vcoreid = ev_q->ev_vcore;       /* use the ev_q's vcoreid */
385         /* Note that RR overwrites APPRO */
386         if (ev_q->ev_flags & EVENT_ROUNDROBIN) {
387                 /* Pick a vcore, round-robin style.  Assuming ev_vcore was the previous
388                  * one used.  Note that round-robin overrides the passed-in vcoreid.
389                  * Also note this may be 'wrong' if num_vcores changes. */
390                 vcoreid = (ev_q->ev_vcore + 1) % p->procinfo->num_vcores;
391                 ev_q->ev_vcore = vcoreid;
392         }
393         if (!vcoreid_is_safe(vcoreid)) {
394                 /* Ought to kill them, just warn for now */
395                 printk("[kernel] Vcoreid %d unsafe! (too big?)\n", vcoreid);
396                 goto out;
397         }
398         /* If we're a SPAM_PUBLIC, they just want us to spam the message.  Note we
399          * don't care about the mbox, since it'll go to VCPD public mboxes, and
400          * we'll prefer to send it to whatever vcoreid we determined at this point
401          * (via APPRO or whatever). */
402         if (ev_q->ev_flags & EVENT_SPAM_PUBLIC) {
403                 spam_public_msg(p, msg, vcoreid, ev_q->ev_flags & EVENT_SPAM_FLAGS);
404                 goto out;
405         }
406         /* We aren't spamming and we know the default vcore, and now we need to
407          * figure out which mbox to use.  If they provided an mbox, we'll use it.
408          * If not, we'll use a VCPD mbox (public or private, depending on the
409          * flags). */
410         ev_mbox = ev_q->ev_mbox;
411         if (!ev_mbox)
412                 ev_mbox = get_vcpd_mbox(vcoreid, ev_q->ev_flags);
413         /* At this point, we ought to have the right mbox to send the msg to, and
414          * which vcore to alert (IPI/INDIR) (if applicable).  The mbox could be the
415          * vcore's vcpd ev_mbox. */
416         if (!ev_mbox) {
417                 /* This shouldn't happen any more, this is more for sanity's sake */
418                 warn("[kernel] ought to have an mbox by now!");
419                 goto out;
420         }
421         /* Even if we're using an mbox in procdata (VCPD), we want a user pointer */
422         if (!is_user_rwaddr(ev_mbox, sizeof(struct event_mbox))) {
423                 /* Ought to kill them, just warn for now */
424                 printk("[kernel] Illegal addr for ev_mbox\n");
425                 goto out;
426         }
427         /* We used to support no msgs, but quit being lazy and send a 'msg'.  If the
428          * ev_q is a NOMSG, we won't actually memcpy or anything, it'll just be a
429          * vehicle for sending the ev_type. */
430         assert(msg);
431         post_ev_msg(p, ev_mbox, msg, ev_q->ev_flags);
432         wmb();  /* ensure ev_msg write is before alerting the vcore */
433         /* Prod/alert a vcore with an IPI or INDIR, if desired.  INDIR will also
434          * call try_notify (IPI) later */
435         if (ev_q->ev_flags & EVENT_INDIR) {
436                 send_indir(p, ev_q, vcoreid);
437         } else {
438                 /* they may want an IPI despite not wanting an INDIR */
439                 try_notify(p, vcoreid, ev_q->ev_flags);
440         }
441         /* Fall through */
442 out:
443         /* Return to the old address space. */
444         switch_back(p, old_proc);
445 }
446
447 /* Send an event for the kernel event ev_num.  These are the "one sided" kernel
448  * initiated events, that require a lookup of the ev_q in procdata.  This is
449  * roughly equivalent to the old "proc_notify()" */
450 void send_kernel_event(struct proc *p, struct event_msg *msg, uint32_t vcoreid)
451 {
452         uint16_t ev_num = msg->ev_type;
453         assert(ev_num < MAX_NR_EVENT);          /* events start at 0 */
454         struct event_queue *ev_q = p->procdata->kernel_evts[ev_num];
455         /* linux would put a rmb_depends() here too, i think. */
456         if (ev_q)
457                 send_event(p, ev_q, msg, vcoreid);
458 }
459
460 /* Writes the msg to the vcpd mbox of the vcore.  If you want the private mbox,
461  * send in the ev_flag EVENT_VCORE_PRIVATE.  If not, the message could
462  * be received by other vcores if the given vcore is offline/preempted/etc.
463  * Whatever other flags you pass in will get sent to post_ev_msg.  Currently,
464  * the only one that will get looked at is NO_MSG (set a bit).
465  *
466  * This needs to load current (switch_to), but doesn't need to care about what
467  * the process wants.  Note this isn't commonly used - just the monitor and
468  * sys_self_notify(). */
469 void post_vcore_event(struct proc *p, struct event_msg *msg, uint32_t vcoreid,
470                       int ev_flags)
471 {
472         /* Need to set p as current to post the event */
473         struct per_cpu_info *pcpui = &per_cpu_info[core_id()];
474         struct proc *old_proc = switch_to(p);
475         /* *ev_mbox is the user address of the vcpd mbox */
476         post_vc_msg(p, vcoreid, get_vcpd_mbox(vcoreid, ev_flags), msg, ev_flags);
477         switch_back(p, old_proc);
478 }
479
480 /* Attempts to send a posix signal to the process.  If they do not have an ev_q
481  * registered for EV_POSIX_SIGNAL, then nothing will happen. */
482 void send_posix_signal(struct proc *p, int sig_nr)
483 {
484         struct event_msg local_msg = {0};
485         local_msg.ev_type = EV_POSIX_SIGNAL;
486         local_msg.ev_arg1 = sig_nr;
487         send_kernel_event(p, &local_msg, 0);
488 }