Makes virtio_ring.h a kernel header (XCC)
[akaros.git] / user / vmm / virtio_ring.c
1 /* Virtio ring implementation.
2  *
3  *  Copyright 2007 Rusty Russell IBM Corporation
4  *
5  *  This program is free software; you can redistribute it and/or modify
6  *  it under the terms of the GNU General Public License as published by
7  *  the Free Software Foundation; either version 2 of the License, or
8  *  (at your option) any later version.
9  *
10  *  This program is distributed in the hope that it will be useful,
11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13  *  GNU General Public License for more details.
14  *
15  *  You should have received a copy of the GNU General Public License
16  *  along with this program; if not, write to the Free Software
17  *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
18  */
19 #include <stdio.h>
20 #include <sys/types.h>
21 #include <sys/stat.h>
22 #include <fcntl.h>
23 #include <unistd.h>
24 #include <errno.h>
25 #include <stdlib.h>
26 #include <string.h>
27 #include <sys/uio.h>
28 #include <stdint.h>
29 #include <err.h>
30 #include <sys/mman.h>
31 #include <vmm/virtio.h>
32
33 #define BAD_RING(_vq, fmt, args...)                             \
34         do {                                                    \
35         fprintf(stderr, "%s:"fmt, (_vq)->vq.name, ##args);      \
36         while (1); \
37         } while (0)
38 /* Caller is supposed to guarantee no reentry. */
39 #define START_USE(_vq)                                          \
40         do {                                                    \
41                 if ((_vq)->in_use){                             \
42                         fprintf(stderr, "%s:in_use = %i\n",     \
43                               (_vq)->vq.name, (_vq)->in_use);   \
44                         exit(1);                                \
45                 }                                               \
46                 (_vq)->in_use = __LINE__;                       \
47         } while (0)
48 #define BUG_ON(x) do { if (x) {fprintf(stderr, "bug\n"); while (1);} } while (0)
49 #define END_USE(_vq) \
50         do { BUG_ON(!(_vq)->in_use); (_vq)->in_use = 0; } while(0)
51
52 struct vring_virtqueue {
53         struct virtqueue vq;
54
55         /* Actual memory layout for this queue */
56         struct vring vring;
57
58         /* Can we use weak barriers? */
59         bool weak_barriers;
60
61         /* Other side has made a mess, don't try any more. */
62         bool broken;
63
64         /* Host supports indirect buffers */
65         bool indirect;
66
67         /* Host publishes avail event idx */
68         bool event;
69
70         /* Head of free buffer list. */
71         unsigned int free_head;
72         /* Number we've added since last sync. */
73         unsigned int num_added;
74
75         /* Last used index we've seen. */
76         uint16_t last_used_idx;
77
78         uint16_t last_avail_idx;
79
80         /* How to notify other side. FIXME: commonalize hcalls! */
81          bool(*notify) (struct virtqueue * vq);
82
83         /* They're supposed to lock for us. */
84         unsigned int in_use;
85
86         /* Figure out if their kicks are too delayed. */
87         bool last_add_time_valid;
88         uint64_t last_add_time;
89
90         /* Tokens for callbacks. */
91         void *data[];
92 };
93
94 /* Return the container/struct holding the object 'ptr' points to */
95
96 #define container_of(ptr, type, member) ({                                     \
97         (type*)((char*)ptr - offsetof(type, member));                             \
98 })
99 #define to_vvq(_vq) container_of(_vq, struct vring_virtqueue, vq)
100
101 static inline struct scatterlist *sg_next_chained(struct scatterlist *sg,
102                                                                                                   unsigned int *count)
103 {
104         return NULL;
105 }
106
107 static inline struct scatterlist *sg_next_arr(struct scatterlist *sg,
108                                                                                           unsigned int *count)
109 {
110         if (--(*count) == 0)
111                 return NULL;
112         return sg + 1;
113 }
114
115 /* Set up an indirect table of descriptors and add it to the queue. */
116 static inline int vring_add_indirect(struct vring_virtqueue *vq,
117                                                                          struct scatterlist *sgs[],
118                                                                          struct scatterlist *(*next)
119                                                                           (struct scatterlist *, unsigned int *),
120                                                                          unsigned int total_sg,
121                                                                          unsigned int total_out,
122                                                                          unsigned int total_in,
123                                                                          unsigned int out_sgs,
124                                                                          unsigned int in_sgs, int flags)
125 {
126         struct vring_desc *desc;
127         unsigned head;
128         struct scatterlist *sg;
129         int i, n;
130
131         /*
132          * We require lowmem mappings for the descriptors because
133          * otherwise virt_to_phys will give us bogus addresses in the
134          * virtqueue.
135          */
136         flags = 0;
137
138         desc = calloc(total_sg, sizeof(struct vring_desc));
139         if (!desc)
140                 return -ENOMEM;
141
142         /* Transfer entries from the sg lists into the indirect page */
143         i = 0;
144         for (n = 0; n < out_sgs; n++) {
145                 for (sg = sgs[n]; sg; sg = next(sg, &total_out)) {
146                         desc[i].flags = VRING_DESC_F_NEXT;
147                         desc[i].addr = sg_phys(sg->v);
148                         desc[i].len = sg->length;
149                         desc[i].next = i + 1;
150                         i++;
151                 }
152         }
153         for (; n < (out_sgs + in_sgs); n++) {
154                 for (sg = sgs[n]; sg; sg = next(sg, &total_in)) {
155                         desc[i].flags = VRING_DESC_F_NEXT | VRING_DESC_F_WRITE;
156                         desc[i].addr = sg_phys(sg->v);
157                         desc[i].len = sg->length;
158                         desc[i].next = i + 1;
159                         i++;
160                 }
161         }
162         BUG_ON(i != total_sg);
163
164         /* Last one doesn't continue. */
165         desc[i - 1].flags &= ~VRING_DESC_F_NEXT;
166         desc[i - 1].next = 0;
167
168         /* We're about to use a buffer */
169         vq->vq.num_free--;
170
171         /* Use a single buffer which doesn't continue */
172         head = vq->free_head;
173         vq->vring.desc[head].flags = VRING_DESC_F_INDIRECT;
174         vq->vring.desc[head].addr = virt_to_phys(desc);
175         /* kmemleak gives a false positive, as it's hidden by virt_to_phys */
176         //kmemleak_ignore(desc);
177         vq->vring.desc[head].len = i * sizeof(struct vring_desc);
178
179         /* Update free pointer */
180         vq->free_head = vq->vring.desc[head].next;
181
182         return head;
183 }
184
185 static inline int virtqueue_add_avail(struct virtqueue *_vq,
186                                                                 struct scatterlist *sgs[],
187                                                                 struct scatterlist *(*next)
188                                                                  (struct scatterlist *, unsigned int *),
189                                                                 unsigned int total_out,
190                                                                 unsigned int total_in,
191                                                                 unsigned int out_sgs,
192                                                                 unsigned int in_sgs, void *data, int flags)
193 {
194         int canary;
195         struct vring_virtqueue *vq = to_vvq(_vq);
196         struct scatterlist *sg;
197         unsigned int i, n, avail, prev = 0, total_sg;
198         int head;
199
200         START_USE(vq);
201
202         BUG_ON(data == NULL);
203
204 #ifdef DEBUG
205         {
206                 ktime_t now = ktime_get();
207
208                 /* No kick or get, with .1 second between?  Warn. */
209                 if (vq->last_add_time_valid)
210                         WARN_ON(ktime_to_ms(ktime_sub(now, vq->last_add_time))
211                                         > 100);
212                 vq->last_add_time = now;
213                 vq->last_add_time_valid = true;
214         }
215 #endif
216
217         total_sg = total_in + total_out;
218
219         /* If the host supports indirect descriptor tables, and we have multiple
220          * buffers, then go indirect. FIXME: tune this threshold */
221         if (vq->indirect && total_sg > 1 && vq->vq.num_free) {
222                 head = vring_add_indirect(vq, sgs, next, total_sg, total_out,
223                                           total_in, out_sgs, in_sgs, flags);
224                 if (head >= 0)
225                         goto add_head;
226         }
227
228         BUG_ON(total_sg > vq->vring.num);
229         BUG_ON(total_sg == 0);
230         canary = vq->vq.num_free;
231
232         if (vq->vq.num_free < total_sg) {
233                 if (0) fprintf(stderr, "Can't add buf len %i - avail = %i\n",
234                                  total_sg, vq->vq.num_free);
235                 /* FIXME: for historical reasons, we force a notify here if
236                  * there are outgoing parts to the buffer.  Presumably the
237                  * host should service the ring ASAP. */
238                 if (out_sgs)
239                         vq->notify(&vq->vq);
240                 END_USE(vq);
241                 return -ENOSPC;
242         }
243         /* We're about to use some buffers from the free list. */
244         vq->vq.num_free -= total_sg;
245
246         head = i = vq->free_head;
247         for (n = 0; n < out_sgs; n++) {
248                 for (sg = sgs[n]; sg; sg = next(sg, &total_out)) {
249                         vq->vring.desc[i].flags = VRING_DESC_F_NEXT;
250                         vq->vring.desc[i].addr = sg_phys(sg->v);
251                         vq->vring.desc[i].len = sg->length;
252                         prev = i;
253                         i = vq->vring.desc[i].next;
254                 }
255         }
256         for (; n < (out_sgs + in_sgs); n++) {
257                 for (sg = sgs[n]; sg; sg = next(sg, &total_in)) {
258                         vq->vring.desc[i].flags = VRING_DESC_F_NEXT | VRING_DESC_F_WRITE;
259                         vq->vring.desc[i].addr = sg_phys(sg->v);
260                         vq->vring.desc[i].len = sg->length;
261                         prev = i;
262                         i = vq->vring.desc[i].next;
263                 }
264         }
265
266         /* Last one doesn't continue. */
267         vq->vring.desc[prev].flags &= ~VRING_DESC_F_NEXT;
268
269         /* Update free pointer */
270         vq->free_head = i;
271 add_head:
272         /* Set token. */
273         vq->data[head] = data;
274         /* Put entry in available array (but don't update avail->idx until they
275          * do sync). */
276         avail = (vq->vring.avail->idx & (vq->vring.num - 1));
277         vq->vring.avail->ring[avail] = head;
278         /* Descriptors and available array need to be set before we expose the
279          * new available array entries. */
280         virtio_wmb(vq->weak_barriers);
281         vq->vring.avail->idx++;
282         vq->num_added++;
283
284         /* This is very unlikely, but theoretically possible.  Kick
285          * just in case. */
286         if (unlikely(vq->num_added == (1 << 16) - 1))
287                 virtqueue_kick(_vq);
288
289         if (0) fprintf(stderr, "Added buffer head %i to %p\n", head, vq);
290         END_USE(vq);
291         BUG_ON(vq->vq.num_free > canary);
292         return 0;
293 }
294
295 /**
296  * virtqueue_add_outbuf_avail - expose output buffers to other end
297  * @vq: the struct virtqueue we're talking about.
298  * @sgs: array of scatterlists (need not be terminated!)
299  * @num: the number of scatterlists readable by other side
300  * @data: the token identifying the buffer.
301  * @gfp: how to do memory allocations (if necessary).
302  *
303  * Caller must ensure we don't call this with other virtqueue operations
304  * at the same time (except where noted).
305  *
306  * Returns zero or a negative error (ie. ENOSPC, ENOMEM).
307  */
308 int virtqueue_add_outbuf_avail(struct virtqueue *vq,
309                                                  struct scatterlist sg[], unsigned int num,
310                                                  void *data, int flags)
311 {
312         return virtqueue_add_avail(vq, &sg, sg_next_arr, num, 0, 1, 0, data, flags);
313 }
314
315 /**
316  * virtqueue_add_inbuf_avail - expose input buffers to other end
317  * @vq: the struct virtqueue we're talking about.
318  * @sgs: array of scatterlists (need not be terminated!)
319  * @num: the number of scatterlists writable by other side
320  * @data: the token identifying the buffer.
321  * @gfp: how to do memory allocations (if necessary).
322  *
323  * Caller must ensure we don't call this with other virtqueue operations
324  * at the same time (except where noted).
325  *
326  * Returns zero or a negative error (ie. ENOSPC, ENOMEM).
327  */
328 int virtqueue_add_inbuf_avail(struct virtqueue *vq,
329                                                 struct scatterlist sg[], unsigned int num,
330                                                 void *data, int flags)
331 {
332         return virtqueue_add_avail(vq, &sg, sg_next_arr, 0, num, 0, 1, data, flags);
333 }
334
335 /**
336  * virtqueue_kick_prepare - first half of split virtqueue_kick call.
337  * @vq: the struct virtqueue
338  *
339  * Instead of virtqueue_kick(), you can do:
340  *      if (virtqueue_kick_prepare(vq))
341  *              virtqueue_notify(vq);
342  *
343  * This is sometimes useful because the virtqueue_kick_prepare() needs
344  * to be serialized, but the actual virtqueue_notify() call does not.
345  */
346 bool virtqueue_kick_prepare(struct virtqueue * _vq)
347 {
348         struct vring_virtqueue *vq = to_vvq(_vq);
349         uint16_t new, old;
350         bool needs_kick;
351
352         START_USE(vq);
353         /* We need to expose available array entries before checking avail
354          * event. */
355         virtio_mb(vq->weak_barriers);
356
357         old = vq->vring.avail->idx - vq->num_added;
358         new = vq->vring.avail->idx;
359         vq->num_added = 0;
360
361 #ifdef DEBUG
362         if (vq->last_add_time_valid) {
363                 WARN_ON(ktime_to_ms(ktime_sub(ktime_get(), vq->last_add_time)) > 100);
364         }
365         vq->last_add_time_valid = false;
366 #endif
367
368         if (vq->event) {
369                 needs_kick = vring_need_event(vring_avail_event(&vq->vring), new, old);
370         } else {
371                 needs_kick = !(vq->vring.used->flags & VRING_USED_F_NO_NOTIFY);
372         }
373         END_USE(vq);
374         return needs_kick;
375 }
376
377 /**
378  * virtqueue_notify - second half of split virtqueue_kick call.
379  * @vq: the struct virtqueue
380  *
381  * This does not need to be serialized.
382  *
383  * Returns false if host notify failed or queue is broken, otherwise true.
384  */
385 bool virtqueue_notify(struct virtqueue * _vq)
386 {
387         struct vring_virtqueue *vq = to_vvq(_vq);
388
389         if (unlikely(vq->broken))
390                 return false;
391
392         /* Prod other side to tell it about changes. */
393         if (!vq->notify(_vq)) {
394                 vq->broken = true;
395                 return false;
396         }
397         return true;
398 }
399
400 /**
401  * virtqueue_kick - update after add_buf
402  * @vq: the struct virtqueue
403  *
404  * After one or more virtqueue_add_* calls, invoke this to kick
405  * the other side.
406  *
407  * Caller must ensure we don't call this with other virtqueue
408  * operations at the same time (except where noted).
409  *
410  * Returns false if kick failed, otherwise true.
411  */
412 bool virtqueue_kick(struct virtqueue * vq)
413 {
414         if (virtqueue_kick_prepare(vq))
415                 return virtqueue_notify(vq);
416         return true;
417 }
418
419 static void detach_buf(struct vring_virtqueue *vq, unsigned int head)
420 {
421         unsigned int i;
422
423         /* Clear data ptr. */
424         vq->data[head] = NULL;
425
426         /* Put back on free list: find end */
427         i = head;
428
429         /* Free the indirect table */
430         if (vq->vring.desc[i].flags & VRING_DESC_F_INDIRECT) ;  //kfree(phys_to_virt(vq->vring.desc[i].addr));
431
432         while (vq->vring.desc[i].flags & VRING_DESC_F_NEXT) {
433                 i = vq->vring.desc[i].next;
434                 vq->vq.num_free++;
435         }
436
437         vq->vring.desc[i].next = vq->free_head;
438         vq->free_head = head;
439         /* Plus final descriptor */
440         vq->vq.num_free++;
441 }
442
443 static inline bool more_used(const struct vring_virtqueue *vq)
444 {
445         return vq->last_used_idx != vq->vring.used->idx;
446 }
447
448 /**
449  * virtqueue_get_buf_used - get the next used buffer
450  * @vq: the struct virtqueue we're talking about.
451  * @len: the length written into the buffer
452  *
453  * If the driver wrote data into the buffer, @len will be set to the
454  * amount written.  This means you don't need to clear the buffer
455  * beforehand to ensure there's no data leakage in the case of short
456  * writes.
457  *
458  * Caller must ensure we don't call this with other virtqueue
459  * operations at the same time (except where noted).
460  *
461  * Returns NULL if there are no used buffers, or the "data" token
462  * handed to virtqueue_add_*().
463  */
464 void *virtqueue_get_buf_used(struct virtqueue *_vq, unsigned int *len)
465 {
466         struct vring_virtqueue *vq = to_vvq(_vq);
467         void *ret;
468         unsigned int i;
469         uint16_t last_used;
470
471         START_USE(vq);
472
473         if (unlikely(vq->broken)) {
474                 END_USE(vq);
475                 return NULL;
476         }
477
478         if (!more_used(vq)) {
479                 if (0) fprintf(stderr, "No more buffers in queue\n");
480                 END_USE(vq);
481                 return NULL;
482         }
483
484         /* Only get used array entries after they have been exposed by host. */
485         virtio_rmb(vq->weak_barriers);
486
487         last_used = (vq->last_used_idx & (vq->vring.num - 1));
488         i = vq->vring.used->ring[last_used].id;
489         *len = vq->vring.used->ring[last_used].len;
490
491         if (unlikely(i >= vq->vring.num)) {
492                 BAD_RING(vq, "id %u out of range\n", i);
493                 return NULL;
494         }
495         if (unlikely(!vq->data[i])) {
496                 BAD_RING(vq, "id %u is not a head!\n", i);
497                 return NULL;
498         }
499
500         /* detach_buf clears data, so grab it now. */
501         ret = vq->data[i];
502         detach_buf(vq, i);
503         vq->last_used_idx++;
504         /* If we expect an interrupt for the next entry, tell host
505          * by writing event index and flush out the write before
506          * the read in the next get_buf call. */
507         if (!(vq->vring.avail->flags & VRING_AVAIL_F_NO_INTERRUPT)) {
508                 vring_used_event(&vq->vring) = vq->last_used_idx;
509                 virtio_mb(vq->weak_barriers);
510         }
511 #ifdef DEBUG
512         vq->last_add_time_valid = false;
513 #endif
514
515         END_USE(vq);
516         return ret;
517 }
518
519 /**
520  * virtqueue_disable_cb - disable callbacks
521  * @vq: the struct virtqueue we're talking about.
522  *
523  * Note that this is not necessarily synchronous, hence unreliable and only
524  * useful as an optimization.
525  *
526  * Unlike other operations, this need not be serialized.
527  */
528 void virtqueue_disable_cb(struct virtqueue *_vq)
529 {
530         struct vring_virtqueue *vq = to_vvq(_vq);
531
532         vq->vring.avail->flags |= VRING_AVAIL_F_NO_INTERRUPT;
533 }
534
535 /**
536  * virtqueue_enable_cb_prepare - restart callbacks after disable_cb
537  * @vq: the struct virtqueue we're talking about.
538  *
539  * This re-enables callbacks; it returns current queue state
540  * in an opaque unsigned value. This value should be later tested by
541  * virtqueue_poll, to detect a possible race between the driver checking for
542  * more work, and enabling callbacks.
543  *
544  * Caller must ensure we don't call this with other virtqueue
545  * operations at the same time (except where noted).
546  */
547 unsigned virtqueue_enable_cb_prepare(struct virtqueue *_vq)
548 {
549         struct vring_virtqueue *vq = to_vvq(_vq);
550         uint16_t last_used_idx;
551
552         START_USE(vq);
553
554         /* We optimistically turn back on interrupts, then check if there was
555          * more to do. */
556         /* Depending on the VIRTIO_RING_F_EVENT_IDX feature, we need to
557          * either clear the flags bit or point the event index at the next
558          * entry. Always do both to keep code simple. */
559         vq->vring.avail->flags &= ~VRING_AVAIL_F_NO_INTERRUPT;
560         vring_used_event(&vq->vring) = last_used_idx = vq->last_used_idx;
561         END_USE(vq);
562         return last_used_idx;
563 }
564
565 /**
566  * virtqueue_poll - query pending used buffers
567  * @vq: the struct virtqueue we're talking about.
568  * @last_used_idx: virtqueue state (from call to virtqueue_enable_cb_prepare).
569  *
570  * Returns "true" if there are pending used buffers in the queue.
571  *
572  * This does not need to be serialized.
573  */
574 bool virtqueue_poll_used(struct virtqueue * _vq, unsigned last_used_idx)
575 {
576         struct vring_virtqueue *vq = to_vvq(_vq);
577
578         virtio_mb(vq->weak_barriers);
579         return (uint16_t) last_used_idx != vq->vring.used->idx;
580 }
581
582 /**
583  * virtqueue_enable_cb - restart callbacks after disable_cb.
584  * @vq: the struct virtqueue we're talking about.
585  *
586  * This re-enables callbacks; it returns "false" if there are pending
587  * buffers in the queue, to detect a possible race between the driver
588  * checking for more work, and enabling callbacks.
589  *
590  * Caller must ensure we don't call this with other virtqueue
591  * operations at the same time (except where noted).
592  */
593 bool virtqueue_enable_cb(struct virtqueue * _vq)
594 {
595         unsigned last_used_idx = virtqueue_enable_cb_prepare(_vq);
596         return !virtqueue_poll_used(_vq, last_used_idx);
597 }
598
599 /**
600  * virtqueue_enable_cb_delayed - restart callbacks after disable_cb.
601  * @vq: the struct virtqueue we're talking about.
602  *
603  * This re-enables callbacks but hints to the other side to delay
604  * interrupts until most of the available buffers have been processed;
605  * it returns "false" if there are many pending buffers in the queue,
606  * to detect a possible race between the driver checking for more work,
607  * and enabling callbacks.
608  *
609  * Caller must ensure we don't call this with other virtqueue
610  * operations at the same time (except where noted).
611  */
612 bool virtqueue_enable_cb_delayed(struct virtqueue * _vq)
613 {
614         struct vring_virtqueue *vq = to_vvq(_vq);
615         uint16_t bufs;
616
617         START_USE(vq);
618
619         /* We optimistically turn back on interrupts, then check if there was
620          * more to do. */
621         /* Depending on the VIRTIO_RING_F_USED_EVENT_IDX feature, we need to
622          * either clear the flags bit or point the event index at the next
623          * entry. Always do both to keep code simple. */
624         vq->vring.avail->flags &= ~VRING_AVAIL_F_NO_INTERRUPT;
625         /* TODO: tune this threshold */
626         bufs = (uint16_t) (vq->vring.avail->idx - vq->last_used_idx) * 3 / 4;
627         vring_used_event(&vq->vring) = vq->last_used_idx + bufs;
628         virtio_mb(vq->weak_barriers);
629         if (unlikely((uint16_t) (vq->vring.used->idx - vq->last_used_idx) > bufs)) {
630                 END_USE(vq);
631                 return false;
632         }
633
634         END_USE(vq);
635         return true;
636 }
637
638 /**
639  * virtqueue_detach_unused_buf - detach first unused buffer
640  * @vq: the struct virtqueue we're talking about.
641  *
642  * Returns NULL or the "data" token handed to virtqueue_add_*().
643  * This is not valid on an active queue; it is useful only for device
644  * shutdown.
645  */
646 void *virtqueue_detach_unused_buf(struct virtqueue *_vq)
647 {
648         struct vring_virtqueue *vq = to_vvq(_vq);
649         unsigned int i;
650         void *buf;
651
652         START_USE(vq);
653
654         for (i = 0; i < vq->vring.num; i++) {
655                 if (!vq->data[i])
656                         continue;
657                 /* detach_buf clears data, so grab it now. */
658                 buf = vq->data[i];
659                 detach_buf(vq, i);
660                 vq->vring.avail->idx--;
661                 END_USE(vq);
662                 return buf;
663         }
664         /* That should have freed everything. */
665         BUG_ON(vq->vq.num_free != vq->vring.num);
666
667         END_USE(vq);
668         return NULL;
669 }
670
671 struct virtqueue *vring_new_virtqueue(unsigned int index,
672                                                                           unsigned int num,
673                                                                           unsigned int vring_align,
674                                                                           bool weak_barriers,
675                                                                           void *pages,
676                                                                           bool(*notify) (struct virtqueue *),
677                                                                           void (*callback) (struct virtqueue *),
678                                                                           const char *name)
679 {
680         struct vring_virtqueue *vq;
681         unsigned int i;
682
683         /* We assume num is a power of 2. */
684         if (num & (num - 1)) {
685                 if (0) fprintf(stderr, "Bad virtqueue length %u\n", num);
686                 exit(1);
687         }
688
689         vq = mmap((int*)4096, sizeof(*vq) + sizeof(void *) * num + 2*PGSIZE, PROT_READ | PROT_WRITE,
690                   MAP_ANONYMOUS, -1, 0);
691         if (vq == MAP_FAILED) {
692                 perror("Unable to mmap vq");
693                 exit(1);
694         }
695
696         fprintf(stderr, "VQ %p %d bytes \n", vq, sizeof(*vq) + sizeof(void *) * num + 2*PGSIZE);
697         if (!vq)
698                 return NULL;
699
700         vring_init(&vq->vring, num, pages, vring_align);
701         fprintf(stderr, "done vring init\n");
702         vq->vq.callback = callback;
703         vq->vq.name = name;
704         vq->vq.num_free = num;
705         vq->vq.index = index;
706         vq->notify = notify;
707         vq->weak_barriers = weak_barriers;
708         vq->broken = false;
709         vq->last_used_idx = 0;
710         vq->num_added = 0;
711 #ifdef DEBUG
712         vq->in_use = false;
713         vq->last_add_time_valid = false;
714 #endif
715
716         vq->indirect = 0;       // virtio_has_feature(vdev, VIRTIO_RING_F_INDIRECT_DESC);
717         vq->event = 0;  //virtio_has_feature(vdev, VIRTIO_RING_F_EVENT_IDX);
718
719         /* No callback?  Tell other side not to bother us. */
720         if (!callback)
721                 vq->vring.avail->flags |= VRING_AVAIL_F_NO_INTERRUPT;
722
723         /* Put everything in free lists. */
724         vq->free_head = 0;
725         for (i = 0; i < num - 1; i++) {
726                 vq->vring.desc[i].next = i + 1;
727                 vq->data[i] = NULL;
728         }
729         vq->data[i] = NULL;
730
731         return &vq->vq;
732 }
733
734 void vring_del_virtqueue(struct virtqueue *vq)
735 {
736
737 }
738
739 #if 0
740 /* Manipulates transport-specific feature bits. */
741 void vring_transport_features(struct virtio_device *vdev)
742 {
743         unsigned int i;
744
745         for (i = VIRTIO_TRANSPORT_F_START; i < VIRTIO_TRANSPORT_F_END; i++) {
746                 switch (i) {
747                         case VIRTIO_RING_F_INDIRECT_DESC:
748                                 break;
749                         case VIRTIO_RING_F_EVENT_IDX:
750                                 break;
751                         default:
752                                 /* We don't understand this bit. */
753                                 clear_bit(i, vdev->features);
754                 }
755         }
756 }
757 #endif
758 /**
759  * virtqueue_get_vring_size - return the size of the virtqueue's vring
760  * @vq: the struct virtqueue containing the vring of interest.
761  *
762  * Returns the size of the vring.  This is mainly used for boasting to
763  * userspace.  Unlike other operations, this need not be serialized.
764  */
765 unsigned int virtqueue_get_vring_size(struct virtqueue *_vq)
766 {
767
768         struct vring_virtqueue *vq = to_vvq(_vq);
769
770         return vq->vring.num;
771 }
772
773 bool virtqueue_is_broken(struct virtqueue * _vq)
774 {
775         struct vring_virtqueue *vq = to_vvq(_vq);
776
777         return vq->broken;
778 }
779
780
781 /* new stuff. This is now more symmetric. */
782
783 int avail(struct virtqueue *_vq)
784 {
785         struct vring_virtqueue *vq = to_vvq(_vq);
786         return vq->vring.avail->idx;
787 }
788
789 void showvq(struct virtqueue *_vq)
790 {
791         struct vring_virtqueue *vq = to_vvq(_vq);
792         struct vring_desc *desc = vq->vring.desc;
793         struct vring_avail *a = vq->vring.avail;
794         struct vring_used *u = vq->vring.used;
795
796 //      int i;
797         fprintf(stderr, "vq %p, desc %p, avail %p, used %p broken %d\n", vq, desc, a, u, vq->broken);
798         fprintf(stderr, "vq; %s, index 0x%x, num_free 0x%x, priv %p\n", vq->vq.name, vq->vq.index, vq->vq.num_free, vq->vq.priv);
799         fprintf(stderr, "avail: flags 0x%x idx 0x%x\n", a->flags, a->idx);
800         fprintf(stderr, "used: flags 0x%x idx 0x%x \n", u->flags, u->idx);
801 }
802
803 void showdesc(struct virtqueue *_vq, uint16_t head)
804 {
805         struct vring_virtqueue *vq = to_vvq(_vq);
806         struct vring_desc *d = &vq->vring.desc[head];
807
808         while (1) {
809                 fprintf(stderr, "%d(%p): %p 0x%x 0x%x[", head, d, (void *)d->addr, d->len, d->flags);
810                 if (d->flags & VRING_DESC_F_WRITE)
811                         fprintf(stderr, "W");
812                 else
813                         fprintf(stderr, "R");
814                 if (d->flags & VRING_DESC_F_INDIRECT)
815                         fprintf(stderr, "I");
816                 fprintf(stderr, "]");
817                 if (d->flags & VRING_DESC_F_NEXT)
818                         fprintf(stderr, "->0x%x,", d->next);
819                 else
820                         break;
821                 d++;
822                 head++;
823                 head = head & (vq->vring.num - 1);
824         }
825         fprintf(stderr, "\n");
826
827 }
828
829 /* This gets the next entry in the queue as one sglist.
830  * we should probably mirror the
831  * in linux virtio they have all kinds of tricks they play to avoid
832  * vmexits and such on virtio. I don't care. The whole point of this is
833  * to avoid vmexits but leave the VMMCP active on the cores. We're
834  * going to be in a core rich world and putting in timesharing hacks
835  * makes no sense.
836  */
837 int virtio_get_buf_avail_start(struct virtqueue *_vq, uint16_t *last_avail_idx, struct scatterlist **sgp, int *sgplen)
838 {
839         struct scatterlist *sg;
840         struct vring_virtqueue *vq = to_vvq(_vq);
841         uint16_t avail_idx, i, head;
842         int sglen;
843 //      int err;
844
845         avail_idx = vq->vring.avail->idx;
846
847         if (*last_avail_idx == avail_idx)
848                 return vq->vring.num;
849
850         /* coherence here: Only get avail ring entries after they have been exposed by guest. */
851
852         i = *last_avail_idx & (vq->vring.num - 1);
853
854         head = vq->vring.avail->ring[i];
855
856         if (head >= vq->vring.num) {
857                 if (0) fprintf(stderr, "Guest says index %u > %u is available",
858                            head, vq->vring.num);
859                 return -EINVAL;
860         }
861
862         (*last_avail_idx)++;
863
864         struct vring_desc *d = vq->vring.desc;
865         for(i = head, sglen = 1; d[i].flags & VRING_DESC_F_NEXT; sglen++) {
866                 i++;
867                 i = i & (vq->vring.num - 1);
868         }
869
870         if (sgp) {
871                 if (0) fprintf(stderr, "entry @%d is %d long\n", head, sglen);
872
873                 sg = calloc(sglen, sizeof(*sg));
874                 *sgp = sg;
875                 *sgplen = sglen;
876
877                 for(i = head; sglen; sglen--) {
878                         sg->v = (void *)d[i].addr;
879                         sg->length = d[i].len;
880                         i++;
881                         sg++;
882                         i = i & (vq->vring.num - 1);
883                 }
884         }
885         return head;
886 }
887
888
889 void virtio_get_buf_avail_done(struct virtqueue *_vq, uint16_t last_avail_idx, int id, int len)
890 {
891         struct vring_virtqueue *vq = to_vvq(_vq);
892         /* consume it. */
893         struct vring_used *u = vq->vring.used;
894         u->ring[u->idx].id = id;
895         u->ring[u->idx].len = len;
896         u->idx = (u->idx + 1) % vq->vring.num;
897 }
898
899 #define lg_last_avail(vq)       ((vq)->last_avail_idx)
900 #define guest_limit ((1ULL<<48)-1)
901 /*L:200
902  * Device Handling.
903  *
904  * When the Guest gives us a buffer, it sends an array of addresses and sizes.
905  * We need to make sure it's not trying to reach into the Launcher itself, so
906  * we have a convenient routine which checks it and exits with an error message
907  * if something funny is going on:
908  */
909 static void *_check_pointer(unsigned long addr, unsigned int size,
910                             unsigned int line)
911 {
912         /*
913          * Check if the requested address and size exceeds the allocated memory,
914          * or addr + size wraps around.
915          */
916         if ((addr + size) > guest_limit || (addr + size) < addr)
917                 errx(1, "%s:%i: Invalid address %#lx", __FILE__, line, addr);
918         /*
919          * We return a pointer for the caller's convenience, now we know it's
920          * safe to use.
921          */
922         return (void *)addr;
923 }
924 /* A macro which transparently hands the line number to the real function. */
925 #define check_pointer(addr,size) _check_pointer(addr, size, __LINE__)
926
927 /*
928  * Each buffer in the virtqueues is actually a chain of descriptors.  This
929  * function returns the next descriptor in the chain, or vq->vring.num if we're
930  * at the end.
931  */
932 static unsigned next_desc(struct vring_desc *desc,
933                           unsigned int i, unsigned int max)
934 {
935         unsigned int next;
936
937         /* If this descriptor says it doesn't chain, we're done. */
938         if (!(desc[i].flags & VRING_DESC_F_NEXT))
939                 return max;
940
941         /* Check they're not leading us off end of descriptors. */
942         next = desc[i].next;
943         /* Make sure compiler knows to grab that: we don't want it changing! */
944         wmb();
945
946         if (next >= max)
947                 errx(1, "Desc next is %u", next);
948
949         return next;
950 }
951
952 /*
953  * This looks in the virtqueue for the first available buffer, and converts
954  * it to an iovec for convenient access.  Since descriptors consist of some
955  * number of output then some number of input descriptors, it's actually two
956  * iovecs, but we pack them into one and note how many of each there were.
957  *
958  * This function waits if necessary, and returns the descriptor number found.
959  */
960 unsigned int wait_for_vq_desc(struct virtqueue *_vq,
961                                  struct scatterlist iov[],
962                                  unsigned int *out_num, unsigned int *in_num)
963 {
964         struct vring_virtqueue *vq = to_vvq(_vq);
965         unsigned int i, head, max;
966         struct vring_desc *desc;
967         uint16_t last_avail = lg_last_avail(vq);
968
969         *out_num = *in_num = 0;
970         /* There's nothing available? */
971         while (last_avail == vq->vring.avail->idx) {
972                 //uint64_t event;
973                 if (virtqueue_is_broken(_vq)) {
974                         return 0;
975                 }
976
977                 /*
978                  * Since we're about to sleep, now is a good time to tell the
979                  * Guest about what we've used up to now.
980
981                 trigger_irq(vq);
982                  */
983                 /* OK, now we need to know about added descriptors. */
984                 vq->vring.used->flags &= ~VRING_USED_F_NO_NOTIFY;
985
986                 /*
987                  * They could have slipped one in as we were doing that: make
988                  * sure it's written, then check again.
989                  */
990                 mb();
991                 if (last_avail != vq->vring.avail->idx) {
992                         vq->vring.used->flags |= VRING_USED_F_NO_NOTIFY;
993                         break;
994                 }
995
996                 /* Nothing new?  Wait for eventfd to tell us they refilled. *
997                 if (read(vq->eventfd, &event, sizeof(event)) != sizeof(event))
998                         errx(1, "Event read failed?");
999                 */
1000                 /* We don't need to be notified again. */
1001                 vq->vring.used->flags |= VRING_USED_F_NO_NOTIFY;
1002         }
1003
1004         /* Check it isn't doing very strange things with descriptor numbers. */
1005         if ((uint16_t)(vq->vring.avail->idx - last_avail) > vq->vring.num)
1006                 errx(1, "Guest moved used index from %u to %u",
1007                      last_avail, vq->vring.avail->idx);
1008
1009         /*
1010          * Make sure we read the descriptor number *after* we read the ring
1011          * update; don't let the cpu or compiler change the order.
1012          */
1013         rmb();
1014
1015         /*
1016          * Grab the next descriptor number they're advertising, and increment
1017          * the index we've seen.
1018          */
1019         head = vq->vring.avail->ring[last_avail % vq->vring.num];
1020         lg_last_avail(vq)++;
1021
1022         /* If their number is silly, that's a fatal mistake. */
1023         if (head >= vq->vring.num)
1024                 errx(1, "Guest says index %u is available", head);
1025
1026         /* When we start there are none of either input nor output. */
1027         *out_num = *in_num = 0;
1028
1029         max = vq->vring.num;
1030         desc = vq->vring.desc;
1031         i = head;
1032
1033         /*
1034          * We have to read the descriptor after we read the descriptor number,
1035          * but there's a data dependency there so the CPU shouldn't reorder
1036          * that: no rmb() required.
1037          */
1038
1039         /*
1040          * If this is an indirect entry, then this buffer contains a descriptor
1041          * table which we handle as if it's any normal descriptor chain.
1042          */
1043         if (desc[i].flags & VRING_DESC_F_INDIRECT) {
1044                 if (desc[i].len % sizeof(struct vring_desc))
1045                         errx(1, "Invalid size for indirect buffer table");
1046
1047                 max = desc[i].len / sizeof(struct vring_desc);
1048                 // take our chances.
1049                 desc = check_pointer(desc[i].addr, desc[i].len);
1050                 i = 0;
1051         }
1052
1053         do {
1054                 /* Grab the first descriptor, and check it's OK. */
1055                 iov[*out_num + *in_num].length = desc[i].len;
1056                 iov[*out_num + *in_num].v
1057                         = check_pointer(desc[i].addr, desc[i].len);
1058                 /* If this is an input descriptor, increment that count. */
1059                 if (desc[i].flags & VRING_DESC_F_WRITE)
1060                         (*in_num)++;
1061                 else {
1062                         /*
1063                          * If it's an output descriptor, they're all supposed
1064                          * to come before any input descriptors.
1065                          */
1066                         if (*in_num)
1067                                 errx(1, "Descriptor has out after in");
1068                         (*out_num)++;
1069                 }
1070
1071                 /* If we've got too many, that implies a descriptor loop. */
1072                 if (*out_num + *in_num > max)
1073                         errx(1, "Looped descriptor");
1074         } while ((i = next_desc(desc, i, max)) != max);
1075
1076         return head;
1077 }
1078
1079 /*
1080  * After we've used one of their buffers, we tell the Guest about it.  Sometime
1081  * later we'll want to send them an interrupt using trigger_irq(); note that
1082  * wait_for_vq_desc() does that for us if it has to wait.
1083  */
1084 void add_used(struct virtqueue *_vq, unsigned int head, int len)
1085 {
1086         struct vring_virtqueue *vq = to_vvq(_vq);
1087         struct vring_used_elem *used;
1088
1089         /*
1090          * The virtqueue contains a ring of used buffers.  Get a pointer to the
1091          * next entry in that used ring.
1092          */
1093         used = &vq->vring.used->ring[vq->vring.used->idx % vq->vring.num];
1094         used->id = head;
1095         used->len = len;
1096         /* Make sure buffer is written before we update index. */
1097         wmb();
1098         vq->vring.used->idx++;
1099         //vq->pending_used++;
1100 }
1101
1102 void showscatterlist(struct scatterlist *sg, int num)
1103 {
1104         int i;
1105         fprintf(stderr, "%p(0x%x)[", sg, num);
1106         for(i = 0; i < num; i++)
1107                 fprintf(stderr, "[%p, 0x%x],", sg[i].v, sg[i].length);
1108         fprintf(stderr, "]\n");
1109 }
1110
1111 void virtqueue_close(struct virtqueue *_vq)
1112 {
1113         struct vring_virtqueue *vq = to_vvq(_vq);
1114         vq->broken = true;
1115 }