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