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