kconfig: use pkg-config for ncurses detection
[akaros.git] / user / vmm / virtio_lguest_helpers.c
1 /* Virtio helper functions from linux/tools/lguest/lguest.c
2  *
3  * Copyright (C) 1991-2016, the Linux Kernel authors
4  * Copyright (c) 2016 Google Inc.
5  *
6  * Author:
7  *  Rusty Russell <rusty@rustcorp.com.au>
8  *  Michael Taufen <mtaufen@gmail.com>
9  *
10  * This program is free software; you can redistribute it and/or
11  * modify it under the terms of the GNU General Public License as
12  * published by the Free Software Foundation; either version 2 of
13  * the License, or (at your option) any later version.
14  *
15  * This program is distributed in the hope that it will be useful,
16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
18  * GNU General Public License for more details.
19  *
20  * The code from lguest.c has been modified for Akaros.
21  *
22  * Original linux/tools/lguest/lguest.c:
23  *   https://github.com/torvalds/linux/blob/v4.5/tools/lguest/lguest.c
24  *   most recent hash on the file as of v4.5 tag:
25  *     e523caa601f4a7c2fa1ecd040db921baf7453798
26  */
27
28
29 #include <sys/eventfd.h>
30 #include <sys/uio.h>
31 #include <ros/common.h>
32 #include <ros/arch/membar.h>
33 #include <ros/arch/mmu.h>
34 #include <vmm/virtio.h>
35 #include <vmm/virtio_ids.h>
36 #include <vmm/virtio_config.h>
37
38 // The purpose is to make sure the addresses provided by the guest are not
39 // outside the bounds of the guest's memory.
40 // Based on _check_pointer in Linux's lguest.c, which came with
41 // the following comment:
42 /*L:200
43  * Device Handling.
44  *
45  * When the Guest gives us a buffer, it sends an array of addresses and sizes.
46  * We need to make sure it's not trying to reach into the Launcher itself, so
47  * we have a convenient routine which checks it and exits with an error message
48  * if something funny is going on:
49  */
50 void *virtio_check_pointer(struct virtio_vq *vq, uint64_t addr,
51                            uint32_t size, char *file, uint32_t line)
52 {
53         // We check that the pointer + the size doesn't wrap around, and that
54         // the pointer + the size isn't past the top of the guest's address
55         // space.  UVPT is the top of the guest's address space, and is included
56         // from ros/arch/mmu64.h via ros/arch/mmu.h.
57         if ((addr + size) < addr || (addr + size) > UVPT)
58                 VIRTIO_DRI_ERRX(vq->vqdev,
59                         "Driver provided an invalid address or size (addr:0x%x sz:%u).\n"
60                         "  Location: %s:%d", addr, size, file, line);
61
62         return (void *)addr;
63 }
64
65
66 // For traversing the chain of descriptors
67 // Based on next_desc Linux's lguest.c, which came with the following comment:
68 /*
69  * Each buffer in the virtqueues is actually a chain of descriptors.  This
70  * function returns the next descriptor in the chain, or vq->vring.num if we're
71  * at the end.
72  */
73 static uint32_t next_desc(struct vring_desc *desc, uint32_t i, uint32_t max,
74                 struct virtio_vq *vq) // The vq is just for the error message.
75 {
76         uint32_t next;
77
78         // No more in the chain, so return max to signal that we reached the end
79         if (!(desc[i].flags & VRING_DESC_F_NEXT))
80                 return max;
81
82         // TODO: Closely audit the decision to use ACCESS_ONCE() instead of
83         // wmb().
84         //       If we encounter strange problems in the future, it might be
85         //       worth changing it back to a wmb() to see what happens. For the
86         //       record, the virtio console doesn't seem to have any issues
87         //       running without the ACCESS_ONCE() or the wmb(). But they had a
88         //       barrier here, so I'm hesitant to do anything less than
89         //       ACCESS_ONCE().
90
91         // Based on the original comment from lguest:
92         // "Make sure compiler knows to grab that: we don't want it changing!",
93         // it seems that they used a memory barrier after `next = desc[i].next`
94         // to prevent the compiler from returning a `next` that differs from
95         // the `next` that is compared to max. An ACCESS_ONCE() should suffice
96         // to prevent this (see ros/common.h and
97         // http://lwn.net/Articles/508991/).
98         next = ACCESS_ONCE(desc[i].next);
99
100         if (next >= max)
101                 VIRTIO_DRI_ERRX(vq->vqdev,
102                         "The next descriptor index in the chain provided by the driver is outside the bounds of the maximum allowed size of its queue.");
103
104         return next;
105 }
106
107 // Adds descriptor chain to the used ring of the vq
108 // Based on add_used in Linux's lguest.c, which came with the following comment:
109 /*
110  * After we've used one of their buffers, we tell the Guest about it.  Sometime
111  * later we'll want to send them an interrupt using trigger_irq(); note that
112  * wait_for_vq_desc() does that for us if it has to wait.
113  */
114 void virtio_add_used_desc(struct virtio_vq *vq, uint32_t head, uint32_t len)
115 {
116         // virtio-v1.0-cs04 s4.2.2.1 MMIO Device Register Layout
117         if (!vq->qready)
118                 VIRTIO_DEV_ERRX(vq->vqdev,
119                         "The device may not process queues with QueueReady set to 0x0.\n"
120                         "  See virtio-v1.0-cs04 s4.2.2.1 MMIO Device Register Layout");
121
122         // NOTE: len is the total length of the descriptor chain (in bytes)
123         //       that was written to.
124         //       So you should pass 0 if you didn't write anything, and pass
125         //       the number of bytes you wrote otherwise.
126         vq->vring.used->ring[vq->vring.used->idx % vq->vring.num].id = head;
127         vq->vring.used->ring[vq->vring.used->idx % vq->vring.num].len = len;
128
129         // virtio-v1.0-cs04 s2.4.8.2 The Virtqueue Used Ring
130         // TODO: Take note, Barret is thinking about renaming our wmb() to
131         // wwmb()
132         // The device MUST set len prior to updating the used idx, hence wmb()
133         wmb();
134         vq->vring.used->idx++;
135 }
136
137 // Based on wait_for_vq_desc in Linux's'lguest.c, which came with
138 // the following comment:
139 /*
140  * This looks in the virtqueue for the first available buffer, and converts
141  * it to an iovec for convenient access.  Since descriptors consist of some
142  * number of output then some number of input descriptors, it's actually two
143  * iovecs, but we pack them into one and note how many of each there were.
144  *
145  * This function waits if necessary, and returns the descriptor number found.
146  */
147 uint32_t virtio_next_avail_vq_desc(struct virtio_vq *vq, struct iovec iov[],
148                             uint32_t *olen, uint32_t *ilen)
149 {
150 // TODO: Need to make sure we don't overflow iov. Right now we're just kind of
151 //       trusting that whoever provided the iov made it at least as big as
152 //       qnum_max, but maybe we shouldn't be that trusting.
153         uint32_t i, head, max;
154         struct vring_desc *desc;
155         eventfd_t event;
156
157         while (vq->last_avail == vq->vring.avail->idx) {
158                 // We know the ring has updated when idx advances. We check ==
159                 // because idx is allowed to wrap around eventually.
160
161                 // NOTE: lguest kicks the guest with an irq before they wait on
162                 // the eventfd. Instead, I delegate that responsibility to the
163                 // queue service functions.
164
165                 // We're about to wait on the eventfd, so we need to tell the
166                 // guest that we want a notification when it adds new buffers
167                 // for us to process.
168                 vq->vring.used->flags &= ~VRING_USED_F_NO_NOTIFY;
169
170                 // If the guest added an available buffer while we were
171                 // unsetting the VRING_USED_F_NO_NOTIFY flag, we'll break out
172                 // here and process the new buffer.
173                 wrmb();
174                 if (vq->last_avail != vq->vring.avail->idx) {
175                         vq->vring.used->flags |= VRING_USED_F_NO_NOTIFY;
176                         break;
177                 }
178
179                 if (eventfd_read(vq->eventfd, &event))
180                         VIRTIO_DEV_ERRX(vq->vqdev,
181                                 "eventfd read failed while waiting for available descriptors\n");
182
183                 // We don't need the guest to notify us about new buffers unless
184                 // we're waiting on the eventfd, because we will detect the
185                 // updated vq->vring.avail->idx.
186                 vq->vring.used->flags |= VRING_USED_F_NO_NOTIFY;
187         }
188
189         // NOTE: lguest is a bit cryptic about why they check for this.
190         //       They just say, "Check it isn't doing very strange things with
191         //       descriptor numbers."
192         //       I added the reason I believe they do it in this comment and
193         //       the below error message.
194         // The guest can't have incremented idx more than vring.num times since
195         // we last incremented vq->last_avail, because it would have run out of
196         // places to put descriptors after incrementing exactly vring.num times
197         // (prior to our next vq->last_avail++)
198         if ((uint16_t)(vq->vring.avail->idx - vq->last_avail) > vq->vring.num)
199                 VIRTIO_DRI_ERRX(vq->vqdev,
200                                 "vq index increased from %u to %u, exceeded capacity %u\n",
201                                 vq->last_avail, vq->vring.avail->idx,
202                                 vq->vring.num);
203
204         // lguest says here:
205         /*
206          * Make sure we read the descriptor number *after* we read the ring
207          * update; don't let the cpu or compiler change the order.
208          */
209         rmb();
210
211         // Mod because it's a *ring*. lguest said:
212         /*
213          * Grab the next descriptor number they're advertising, and increment
214          * the index we've seen.
215          */
216         head = vq->vring.avail->ring[vq->last_avail % vq->vring.num];
217         vq->last_avail++;
218
219         if (head >= vq->vring.num)
220                 VIRTIO_DRI_ERRX(vq->vqdev,
221                         "The index of the head of the descriptor chain provided by the driver is after the end of the queue.");
222
223         // Don't know how many output buffers or input buffers there are yet,
224         // this depends on the descriptor chain.
225         *olen = *ilen = 0;
226
227         // Since vring.num is the size of the queue, max is the max descriptors
228         // that should be in a descriptor chain. If we find more than that, the
229         // driver is doing something wrong.
230         max = vq->vring.num;
231         desc = vq->vring.desc;
232         i = head;
233
234         // NOTE: (from lguest)
235         /*
236          * We have to read the descriptor after we read the descriptor number,
237          * but there's a data dependency there so the CPU shouldn't reorder
238          * that: no rmb() required.
239          */
240         // Mike: The descriptor number is stored in i; what lguest means is
241         //       that data must flow from avail_ring to head to i before i
242         //       is used to index into desc.
243
244         do {
245                 // If it's an indirect descriptor, it points at a table of
246                 // descriptors provided by the guest driver. The descriptors in
247                 // that table are still chained, so we can ultimately handle
248                 // them the same way as direct descriptors.
249                 if (desc[i].flags & VRING_DESC_F_INDIRECT) {
250
251                         // virtio-v1.0-cs04 s2.4.5.3.1 Indirect Descriptors
252                         if (!(vq->vqdev->dri_feat &
253                               (1<<VIRTIO_RING_F_INDIRECT_DESC)))
254                                 VIRTIO_DRI_ERRX(vq->vqdev,
255                                         "The driver must not set the INDIRECT flag on a descriptor if the INDIRECT_DESC feature was not negotiated.\n"
256                                         "  See virtio-v1.0-cs04 s2.4.5.3.1 Indirect Descriptors");
257
258                         // NOTE: desc is only modified when we detect an
259                         // indirect descriptor, so our implementation works
260                         // whether there is an indirect descriptor at the very
261                         // beginning OR at the very end of the chain
262                         // (virtio-v1.0-cs04 s2.4.5.3.2 compliant)
263                         //
264                         // virtio-v1.0-cs04 s2.4.5.3.1 Indirect Descriptors
265                         if (desc != vq->vring.desc)
266                                 VIRTIO_DRI_ERRX(vq->vqdev,
267                                         "The driver must not set the INDIRECT flag on a descriptor within an indirect descriptor.\n"
268                                         "  See virtio-v1.0-cs04 s2.4.5.3.1 Indirect Descriptors");
269
270                         // virtio-v1.0-cs04 s2.4.5.3.1 Indirect Descriptors
271                         if (desc[i].flags & VRING_DESC_F_NEXT)
272                                 VIRTIO_DRI_ERRX(vq->vqdev,
273                                         "The driver must not set both the INDIRECT and NEXT flags on a descriptor.\n"
274                                         "  See virtio-v1.0-cs04 s2.4.5.3.1 Indirect Descriptors");
275
276                         // nonzero mod indicates wrong table size
277                         if (desc[i].len % sizeof(struct vring_desc))
278                                 VIRTIO_DRI_ERRX(vq->vqdev,
279                                         "The size of a vring descriptor does not evenly divide the length of the indirect table provided by the driver. Bad table size.");
280
281                         // NOTE: virtio-v1.0-cs04 s2.4.5.3.2 Indirect
282                         // Descriptors says that the device MUST ignore the
283                         // write-only flag in the descriptor that refers to an
284                         // indirect table. So we ignore.
285
286                         max = desc[i].len / sizeof(struct vring_desc);
287                         desc = virtio_check_pointer(vq, desc[i].addr,
288                                                     desc[i].len, __FILE__,
289                                                     __LINE__);
290
291                         // Now that desc is pointing at the table of indirect
292                         // descriptors, we set i to 0 so that we can start
293                         // walking that table
294                         i = 0;
295
296                         // virtio-v1.0-cs04 s2.4.5.3.1 Indirect Descriptors
297                         if (max > vq->vring.num) {
298                                 VIRTIO_DRI_ERRX(vq->vqdev,
299                                         "The driver must not create a descriptor chain longer than the queue size of the device.\n"
300                                         "  See virtio-v1.0-cs04 s2.4.5.3.1 Indirect Descriptors");
301                         }
302                 }
303
304                 // Now build the scatterlist of buffers for the device to
305                 // process
306                 iov[*olen + *ilen].iov_len = desc[i].len;
307                 iov[*olen + *ilen].iov_base = virtio_check_pointer(vq,
308                                                                    desc[i].addr,
309                                                                    desc[i].len,
310                                                                    __FILE__,
311                                                                    __LINE__);
312
313                 if (desc[i].flags & VRING_DESC_F_WRITE) {
314                         // input descriptor, increment *ilen
315                         (*ilen)++;
316                 }
317                 else {
318                         // virtio-v1.0-cs04 s2.4.4.2 Message Framing
319                         if (*ilen) {
320                                 VIRTIO_DRI_ERRX(vq->vqdev,
321                                         "Device detected an output descriptor after an input descriptor. The driver must place any device-writeable descriptor elements after all device-readable descriptor elements.\n"
322                                         "  See virtio-v1.0-cs04 s2.4.4.2 Message Framing");
323                         }
324
325                         (*olen)++;
326                 }
327
328                 // virtio-v1.0-cs04 s2.4.5.2 The Virtqueue Descriptor Table
329                 if (*olen + *ilen > max) {
330                         VIRTIO_DRI_ERRX(vq->vqdev,
331                                 "The driver must ensure that there are no loops in the descriptor chain it provides! The combined length of readable and writeable buffers was greater than the number of elements in the queue.\n"
332                                 "  See virtio-v1.0-cs04 s2.4.5.2 The Virtqueue Descriptor Table");
333                 }
334
335
336         } while ((i = next_desc(desc, i, max, vq)) != max);
337
338         return head;
339
340 }
341
342 // Based on check_virtqueue from lguest.c
343 // We call this when the driver writes 0x1 to QueueReady
344 void virtio_check_vring(struct virtio_vq *vq)
345 {
346         // First make sure that the pointers on the vring are all valid:
347         virtio_check_pointer(vq, (uint64_t)vq->vring.desc,
348                              sizeof(*vq->vring.desc) * vq->vring.num,
349                              __FILE__, __LINE__);
350         virtio_check_pointer(vq, (uint64_t)vq->vring.avail,
351                              sizeof(*vq->vring.avail) * vq->vring.num,
352                              __FILE__, __LINE__);
353         virtio_check_pointer(vq, (uint64_t)vq->vring.used,
354                              sizeof(*vq->vring.used) * vq->vring.num,
355                              __FILE__, __LINE__);
356
357
358         // virtio-v1.0-cs04 s2.4.9.1 Virtqueue Notification Suppression
359         if (vq->vring.used->flags != 0)
360                 VIRTIO_DRI_ERRX(vq->vqdev,
361                         "The driver must initialize the flags field of the used ring to 0 when allocating the used ring.\n"
362                         "  See virtio-v1.0-cs04 s2.4.9.1 Virtqueue Notification Suppression");
363 }