Adding some initializations
[barrelfish] / lib / virtio / virtqueue.c
1 /*
2  * Copyright (c) 2014 ETH Zurich.
3  * All rights reserved.
4  *
5  * This file is distributed under the terms in the attached LICENSE file.
6  * If you do not find this file, copies can be found by writing to:
7  * ETH Zurich D-INFK, Universitaetsstrasse 6, CH-8092 Zurich. Attn: Systems Group.
8  */
9 #include <string.h>
10
11 #include <barrelfish/barrelfish.h>
12 #include <barrelfish/waitset.h>
13
14 #include <virtio/virtio.h>
15 #include <virtio/virtio_ring.h>
16 #include <virtio/virtqueue.h>
17 #include <virtio/virtio_device.h>
18
19 #include "vbuffer.h"
20 #include "debug.h"
21
22 #define IS_POW2(num) (((num) != 0) && (((num) & (~(num) + 1)) == (num)))
23
24 #define VIRTQUEUE_FLAG_INDIRECT    1
25 #define VIRTQUEUE_FLAG_EVENT_IDX   2
26 #define VIRTQUEUE_FLAG_ADDED       13
27 #define VIRTQUEUE_FLAG_HAS_BUFFERS 14
28 #define VIRTQUEUE_FLAG_FREE_CAP    15
29
30 /**
31  * this data structure stores additional information to the descriptors
32  */
33 struct vring_desc_info
34 {
35     struct virtio_buffer *buf;
36     void *st;
37     struct virtio_buffer_list *bl;
38     uint8_t is_head;
39
40 };
41
42 /**
43  * this data structure represents a VirtIO queue. It contains additional
44  * information not stored with the vring structure
45  */
46 struct virtqueue
47 {
48     /* device information */
49     struct virtio_device *device;   ///< pointer to to the virtio device
50     uint16_t queue_index;           ///< index of this queue in the device
51     char name[VIRTQUEUE_NAME_SIZE];  ///< name of the queue for debugging
52
53     /* vring  information */
54     struct vring vring;             ///< vring data structure
55     struct capref vring_cap;        ///< capability of the vring data structure
56     lvaddr_t vring_vaddr;           ///< virtual address of the vring in memory
57     lpaddr_t vring_paddr;           ///< physical address of the vring
58     lvaddr_t vring_align;           ///< the alignment of the vring
59
60     uint16_t desc_num;              ///< number of descriptors of this vring
61     uint16_t desc_num_max;          ///< maximum number of descriptors supported
62     uint16_t desc_num_queued;       ///< number of queued used descriptors
63
64     uint16_t free_head;             ///< head of the free descriptor chain
65     uint16_t free_count;            ///< number of available free descriptors
66
67     uint16_t used_tail;             ///< last consumed descriptor used table
68     uint16_t used_head;             ///< caches the head of the used descriptors
69
70     uint32_t flags;                 ///< flags
71
72
73     /* interrupt handling */
74     virtq_intr_hander_t intr_handler;   ///< interrupt handler
75     void *intr_arg;                 ///< user argument for the handler
76
77     struct virtio_buffer_allocator *buffer_alloc;
78     uint8_t buffer_bits;
79     uint8_t header_bits;
80
81     struct vring_desc_info vring_di[0];  ///< array of additional desc information
82 #if 0
83     /* indirect descriptors */
84     uint16_t max_indirect;
85     size_t indirect_size;
86     struct vq_desc_extra {
87         void *cookie; << virtual address?
88         struct vring_desc *indirect;
89         vm_paddr_t indirect_paddr;
90         uint16_t ndescs;
91     }vq_descx[0];
92 #endif
93 };
94
95 /**
96  * \brief sets the interrupt threshold to num_desc processed descriptors
97  *
98  * \param vq        virtqueue to enable the interrupts
99  * \param num_desc  the interrupt threshold
100  *
101  * \returns 1 if the interrupts have been enabled
102  *          0 if the interrupts have not been enabled
103  */
104 static bool virtqueue_interrupt_enable(struct virtqueue *vq,
105                                        uint16_t num_desc)
106 {
107     if (vq->flags & (1 << VIRTQUEUE_FLAG_EVENT_IDX)) {
108         uint16_t *used_event = vring_get_used_event(&vq->vring);
109         *used_event = vq->used_tail + num_desc;
110     } else {
111         vq->vring.avail->flags &= ~VIRTIO_RING_AVAIL_F_NO_INTERRUPT;
112     }
113
114     assert(!"NYI: memory barrier mb()");
115
116     if (virtio_virtqueue_get_num_used(vq) > num_desc) {
117         return 1;
118     }
119
120     return 0;
121 }
122
123 /**
124  * \brief initializes the vring structure of the virtqueue
125  *
126  * \param vq virtqueue of the vring to initialize
127  */
128 static void virtqueue_init_vring(struct virtqueue *vq)
129 {
130     struct vring *vr = &vq->vring;
131
132     assert(vq);
133     assert(vq->desc_num);
134     assert(vq->vring_vaddr);
135
136     /*
137      * initialize the vring structure in memory
138      */
139     vring_init(vr, vq->desc_num, vq->vring_align, (void *) vq->vring_vaddr);
140
141     vr->num = vq->desc_num;
142
143     /*
144      * initialize the descriptor chains
145      */
146     uint32_t i;
147     for (i = 0; i < vq->desc_num; ++i) {
148         vr->desc[i].next = i + 1;
149     }
150     vr->desc[i].next = VIRTQUEUE_CHAIN_END;
151
152 }
153
154 /**
155  * \brief initializes the indirect descriptors
156  *
157  * \param vq the virtqueue to initialize the indirect descriptors
158  * \param size the number of indirect descriptors
159  *
160  * \returns SYS_ERR_OK on success
161  */
162 static errval_t virtqueue_init_indirect(struct virtqueue *vq,
163                                         uint16_t size)
164 {
165     struct virtio_device *vdev = vq->device;
166
167     /*
168      * check if the device supports indirect descriptors first
169      */
170     if (virtio_device_has_feature(vdev, VIRTIO_RING_F_INDIRECT_DESC)) {
171         VIRTIO_DEBUG_VQ("Device does not support indirect descriptors\n");
172         return SYS_ERR_OK;
173     }
174
175     assert(!"NYI: virtqueue_init_indirect");
176
177     return SYS_ERR_OK;
178 }
179
180 static bool virtqueue_should_notify_host(struct virtqueue *vq)
181 {
182     uint16_t new, prev, *event_idx;
183
184     if (vq->flags & (1 << VIRTQUEUE_FLAG_EVENT_IDX)) {
185         new = vq->vring.avail->idx;
186         prev = new - vq->desc_num_queued;
187         event_idx = vring_get_avail_event(&vq->vring);
188
189         return (vring_need_event(*event_idx, new, prev) != 0);
190     }
191
192     return ((vq->vring.used->flags & VIRTIO_RING_USED_F_NO_NOTIFY) == 0);
193 }
194
195 /*
196  * ============================================================================
197  * Public Interface
198  * ============================================================================
199  */
200
201 /*
202  * ----------------------------------------------------------------------------
203  *  Virtqueue Allocation / Deallocation
204  */
205
206 /**
207  * \brief allocates and initiates a new virtqueue structure
208  *
209  * \param setup  pointer to the setup information
210  * \param vq     pointer where to store the new virtqueue pointer
211  *
212  * \returns SYS_ERR_OK on success
213  */
214 errval_t virtio_virtqueue_alloc(struct virtqueue_setup *setup,
215                                 struct virtqueue **vq)
216 {
217     errval_t err;
218
219     VIRTIO_DEBUG_VQ("Allocating VQ(%u) of size %u with buffer of %u bits\n",
220                     setup->queue_id,
221                     setup->vring_ndesc,
222                     setup->buffer_bits);
223
224     assert(vq);
225
226     if (setup->vring_ndesc == 0 || !IS_POW2(setup->vring_ndesc)) {
227         VIRTIO_DEBUG_VQ("ERROR: invalid size: %u\n", setup->vring_ndesc);
228         return VIRTIO_ERR_SIZE_INVALID;
229     }
230
231     size_t size = vring_size(setup->vring_ndesc, setup->vring_align);
232     size = ROUND_UP(size, BASE_PAGE_SIZE);
233
234     if (setup->buffer_bits) {
235         size += setup->vring_ndesc * (1UL << setup->buffer_bits);
236     }
237
238     if (setup->header_bits) {
239         size += setup->vring_ndesc * (1UL << setup->header_bits);
240     }
241
242     struct capref vring_cap;
243     size_t framesize;
244     err = frame_alloc(&vring_cap, size, &framesize);
245     if (err_is_fail(err)) {
246         return err;
247     }
248
249     VIRTIO_DEBUG_VQ("Allocated memory for vring: [0x%lx & 0x%lx]\n",
250                     (uint64_t )size,
251                     (uint64_t )framesize);
252
253     err = virtio_virtqueue_alloc_with_caps(setup, vring_cap, vq);
254     if (err_is_fail(err)) {
255         cap_destroy(vring_cap);
256         return err;
257     }
258
259     /* set the flag that we have allocated the cap, so that it gets free'd */
260     (*vq)->flags |= (1 << VIRTQUEUE_FLAG_FREE_CAP);
261
262     return SYS_ERR_OK;
263 }
264
265 /**
266  * \brief allocates and initiates a new virtqueue structure
267  *
268  * \param setup     pointer to the setup information
269  * \param vring_cap capability to be used for the vring
270  * \param vq        pointer where to store the new virtqueue pointer
271  *
272  * \returns SYS_ERR_OK on success
273  */
274 errval_t virtio_virtqueue_alloc_with_caps(struct virtqueue_setup *setup,
275                                           struct capref vring_cap,
276                                           struct virtqueue **ret_vq)
277 {
278     errval_t err;
279
280     assert(ret_vq);
281
282     if (setup->vring_ndesc == 0 || !IS_POW2(setup->vring_ndesc)) {
283         VIRTIO_DEBUG_VQ("ERROR: invalid size: %u\n", setup->vring_ndesc);
284         return VIRTIO_ERR_SIZE_INVALID;
285     }
286
287     if (setup->max_indirect > VIRTIO_RING_MAX_INDIRECT) {
288         VIRTIO_DEBUG_VQ("ERROR: too many indirect descriptors requested: [%u / %u]\n",
289                         setup->vring_ndesc,
290                         VIRTIO_RING_MAX_INDIRECT);
291         return VIRTIO_ERR_MAX_INDIRECT;
292     }
293
294     setup->vring_align = VIRTQUEUE_ALIGNMENT;
295
296     assert(!capref_is_null(vring_cap));
297
298     struct frame_identity id;
299     err = frame_identify(vring_cap, &id);
300     if (err_is_fail(err)) {
301         return err;
302     }
303
304     size_t vring_mem_size = vring_size(setup->vring_ndesc, setup->vring_align);
305     vring_mem_size = ROUND_UP(vring_mem_size, BASE_PAGE_SIZE);
306
307     if (setup->buffer_bits) {
308         vring_mem_size += setup->vring_ndesc * (1UL << setup->buffer_bits);
309     }
310
311     if (setup->header_bits) {
312         vring_mem_size += setup->vring_ndesc * (1UL << setup->header_bits);
313     }
314
315     if (vring_mem_size > id.bytes) {
316         VIRTIO_DEBUG_VQ("ERROR: supplied cap was too small %lx, needed %lx\n",
317                         (id.bytes),
318                         (uint64_t )vring_mem_size);
319         return VIRTIO_ERR_CAP_SIZE;
320     }
321
322     void *vring_addr;
323     err = vspace_map_one_frame(&vring_addr, vring_mem_size, vring_cap, NULL, NULL);
324     if (err_is_fail(err)) {
325         return err;
326     }
327
328     struct virtqueue *vq;
329
330     vq = calloc(1,
331                 sizeof(struct virtqueue) + (setup->vring_ndesc
332                                 * sizeof(struct vring_desc_info)));
333     if (vq == NULL) {
334         vspace_unmap(vring_addr);
335         return LIB_ERR_MALLOC_FAIL;
336     }
337
338     vq->device = setup->device;
339     strncpy(vq->name, setup->name, sizeof(vq->name));
340     vq->queue_index = setup->queue_id;
341     vq->desc_num = setup->vring_ndesc;
342     vq->vring_align = setup->vring_align;
343     vq->vring_cap = vring_cap;
344     vq->vring_paddr = id.base;
345     vq->vring_vaddr = (lvaddr_t) vring_addr;
346     vq->free_count = setup->vring_ndesc;
347
348     vq->intr_handler = setup->intr_handler;
349     vq->intr_arg = setup->intr_arg;
350
351     if (0 && setup->max_indirect > 0) {
352         /*
353          * TODO: initialize indirect descriptors
354          */
355         virtqueue_init_indirect(vq, setup->max_indirect);
356     }
357
358     if (virtio_device_has_feature(setup->device, VIRTIO_RING_F_EVENT_IDX)) {
359         vq->flags |= (1 << VIRTQUEUE_FLAG_EVENT_IDX);
360     }
361
362     if (setup->buffer_bits) {
363         vq->buffer_bits = setup->buffer_bits;
364         vq->flags |= (1 << VIRTQUEUE_FLAG_HAS_BUFFERS);
365         lpaddr_t offset = vring_size(setup->vring_ndesc, setup->vring_align);
366         offset = ROUND_UP(offset, BASE_PAGE_SIZE);
367         lvaddr_t buf_start = ((lvaddr_t)vring_addr) +offset;
368         VIRTIO_DEBUG_VQ("Allocating %u buffers at offset 0x%lx\n",
369                         setup->vring_ndesc, offset);
370         /* we initialize the first buffer_allocator here  */
371         err = virtio_buffer_alloc_init_vq(&vq->buffer_alloc, vring_cap,buf_start , offset, (1UL<<vq->buffer_bits), setup->vring_ndesc);
372         if (err_is_fail(err)) {
373             DEBUG_ERR(err, "failed to initiate the vbuf allocator");
374         }
375         assert(vq->buffer_bits);
376         assert(vq->buffer_alloc);
377     }
378
379     if (vq->header_bits) {
380         vq->flags |= (1 << VIRTQUEUE_FLAG_HAS_BUFFERS);
381         vq->header_bits = setup->header_bits;
382     }
383
384     virtqueue_init_vring(vq);
385     virtio_virtqueue_intr_disable(vq);
386
387     if (ret_vq) {
388         *ret_vq = vq;
389     }
390
391     return SYS_ERR_OK;
392 }
393
394 /**
395  * \brief frees the resources of previously allocated virtqueues
396  *
397  * \param vq pointer to the virtqueue memory to be freed
398  *
399  * \returns SYS_ERR_OK on success
400  */
401 errval_t virtio_virtqueue_free(struct virtqueue *vq)
402 {
403     assert(!"NYI: virtio_virtqueue_free");
404
405     return SYS_ERR_OK;
406 }
407
408 /*
409  * ----------------------------------------------------------------------------
410  *  Virtqueue Getter Functions
411  */
412
413 /**
414  * \brief Returns the physical address of the vring.
415  *
416  * \param vq pointer to the virtqueue structure
417  *
418  * \returns the physical address of the vring
419  */
420 lpaddr_t virtio_virtqueue_get_vring_paddr(struct virtqueue *vq)
421 {
422     return vq->vring_paddr;
423 }
424
425 /**
426  * \brief returns the alignment of the vring
427  *
428  * \param the virtqueue to get the alignment from
429  *
430  * \returns vring alignment
431  */
432 lvaddr_t virtio_virtqueue_get_vring_align(struct virtqueue *vq)
433 {
434     return vq->vring_align;
435 }
436
437 /**
438  * \brief Returns the frame capability of the vring
439  *
440  * \param vq        pointer to the virtqueue structure
441  * \param ret_cap   memory location where to store the capref
442  */
443 void virtio_virtqueue_get_vring_cap(struct virtqueue *vq,
444                                     struct capref *ret_cap)
445 {
446     if (ret_cap) {
447         *ret_cap = vq->vring_cap;
448     }
449 }
450
451 /**
452  * \brief returns the number of bits if there are alrady allocated buffers
453  *        for this queue
454  *
455  * \param vq the virtqueue
456  *
457  * \returns size of allocated buffers
458  *          0 if none
459  */
460 uint8_t virtio_virtqueue_has_buffers(struct virtqueue *vq)
461 {
462     if (vq->flags & (1 << VIRTQUEUE_FLAG_HAS_BUFFERS)) {
463         return 1;
464     }
465     return 0;
466 }
467
468 /**
469  * \brief returns the virtual base of the previously allocated buffer
470  *
471  * \param vq the virtqueue
472  *
473  * \returns virtual address of allocated buffers
474  *          0 if no buffers are allocated
475  */
476 lvaddr_t virtio_virtqueue_buffer_vbase(struct virtqueue *vq)
477 {
478     if (vq->flags & (1 << VIRTQUEUE_FLAG_HAS_BUFFERS)) {
479         size_t vring_mem_size = vring_size(vq->desc_num, vq->vring_align);
480         vring_mem_size = ROUND_UP(vring_mem_size, BASE_PAGE_SIZE);
481
482         return vq->vring_vaddr + vring_mem_size;
483     }
484     return 0;
485 }
486
487 /**
488  * \brief Returns the number of elements (number of descriptors)in the vring of
489  *        this virtqueue
490  *
491  * \param vq pointer to the virtqueue structure
492  *
493  * \returns number of elements in the vring
494  */
495 uint16_t virtio_virtqueue_get_num_desc(struct virtqueue *vq)
496 {
497     return vq->desc_num;
498 }
499
500 /**
501  * \brief Returns the queue index of the virtqueue of the device
502  *
503  * \param vq pointer to the virtqueue structure
504  *
505  * \returns queue index
506  */
507 uint16_t virtio_virtqueue_get_queue_index(struct virtqueue *vq)
508 {
509     return vq->queue_index;
510 }
511
512 /**
513  * \brief Checks if the virtqueue is empty
514  *
515  * \param vq pointer to the virtqueue structure
516  *
517  * \returns 0 the queue is not empty
518  *          1 the queue is empty
519  */
520 bool virtio_virtqueue_is_empty(struct virtqueue *vq)
521 {
522     return (vq->desc_num == vq->free_count);
523 }
524
525 /**
526  * \brief Checks if the virtqueue is full
527  *
528  * \param vq pointer to the virtqueue structure
529  *
530  * \returns 0 the queue is not full
531  *          1 the queue is full
532  */
533 bool virtio_virtqueue_is_full(struct virtqueue *vq)
534 {
535     return (vq->free_count == 0);
536 }
537
538 /**
539  * \brief Calculates the number of used descriptors in this queue
540  *
541  * \param vq pointer to the virtqueue structure
542  *
543  * \returns number of used descriptors
544  */
545 uint16_t virtio_virtqueue_get_num_used(struct virtqueue *vq)
546 {
547     uint16_t num_used;
548
549     num_used = vq->vring.used->idx - vq->used_tail;
550
551     /* sanity check */
552     assert(num_used <= vq->desc_num);
553
554     return num_used;
555 }
556
557 /*
558  * ----------------------------------------------------------------------------
559  *  Interrupt handling
560  */
561
562 /**
563  * \brief checks if the interrupts can be disabled
564  *
565  * \param vq virtual queue to check
566  *
567  * \returns 1 if the interrupts have been disabled
568  *          0 if the interrupts are not changed
569  *
570  */
571 bool virtio_virtqueue_intr_filter(struct virtqueue *vq)
572 {
573     if (vq->used_tail == vq->vring.used->idx) {
574         return 0;
575     }
576
577     virtio_virtqueue_intr_disable(vq);
578
579     return 1;
580 }
581
582 /**
583  * \brief calls the interrupt handler for this virtqueue
584  *
585  * \param vq virtqueue to call the intr handler for
586  */
587 void virtio_virtqueue_intr_handle(struct virtqueue *vq)
588 {
589     if (vq->intr_handler == NULL) {
590         VIRTIO_DEBUG_VQ("Notice: Interrupt handler is not set\n");
591         return;
592     }
593     vq->intr_handler(vq, vq->intr_arg);
594 }
595
596 /**
597  * \brief enables the interrupts on the next descriptor processed
598  *
599  * \param vq the virtqueue to enable the interrupts
600  *
601  * \returns 1 if the interrupts have been enabled
602  *          0 if the interrupts have not been enabled
603  */
604 bool virtio_virtqueue_intr_enable(struct virtqueue *vq)
605 {
606     return virtqueue_interrupt_enable(vq, 0);
607 }
608
609 /**
610  * \brief postpones the interrupt to a later point of time
611  *
612  * \param vq the virtqueue to enable the interrupts
613  * \param
614  *
615  * \returns 1 if the interrupts have been enabled
616  *          0 if the interrupts have not been enabled
617  */
618 bool virtio_virtqueue_intr_postpone(struct virtqueue *vq,
619                                     enum virtqueue_intr_postpone hint)
620 {
621     uint16_t ndesc = vq->vring.avail->idx - vq->used_tail;
622
623     switch (hint) {
624         case VIRTQUEUE_INTR_POSTPONE_SHORT:
625             ndesc = ndesc / 4;
626             break;
627         case VIRTQUEUE_INTR_POSTPONE_LONG:
628             ndesc = (ndesc * 3) / 4;
629             break;
630         case VIRTQUEUE_INTR_POSTPONE_EMPTIED:
631             break;
632     }
633
634     return virtqueue_interrupt_enable(vq, ndesc);
635 }
636
637 /**
638  * \brief disables the interrupts for the given virtqueue
639  *
640  * \param vq        virtqueue to disable the interrupts
641  */
642 void virtio_virtqueue_intr_disable(struct virtqueue *vq)
643 {
644     if (vq->flags & (1 << VIRTQUEUE_FLAG_EVENT_IDX)) {
645         uint16_t *used_event = vring_get_used_event(&vq->vring);
646         *used_event = vq->used_tail - vq->desc_num - 1;
647     } else {
648         vq->vring.avail->flags |= VIRTIO_RING_AVAIL_F_NO_INTERRUPT;
649     }
650 }
651
652 /**
653  * \brief notifies the host about the new queued descriptors
654  *
655  * \param vq virtqueue to notify the host
656  */
657 void virtio_virtqueue_notify_host(struct virtqueue *vq)
658 {
659     /* TODO: memory barrier */
660     if (virtqueue_should_notify_host(vq)) {
661         virtio_device_notify_host(vq->device, vq->queue_index);
662     }
663     vq->desc_num_queued = 0;
664
665 }
666
667 /*
668  * We layout the vring structure in memory as follows:
669  *
670  * struct vring {
671  *      // The actual descriptors (16 bytes each)
672  *      struct vring_desc desc[num];
673  *
674  *      // A ring of available descriptor heads with free-running index.
675  *      uint16_t avail_flags;
676  *      uint16_t avail_idx;
677  *      uint16_t available[num];
678  *      uint16_t used_event_idx;
679  *
680  *      // Padding to the next align boundary.
681  *      char pad[];
682  *
683  *      // A ring of used descriptor heads with free-running index.
684  *      uint16_t used_flags;
685  *      uint16_t used_idx;
686  *      struct vring_used_elem used[num];
687  *      uint16_t avail_event_idx;
688  * };
689  */
690
691 /**
692  * \brief Maps the given capability and initializes the vring on the memory
693  *        backed by the supplied capability
694  *
695  * \param vr    pointer to the vring structure to be initialized
696  * \param num   the number of elements in the ring
697  * \param align alignment constraints for the vring
698  * \param cap   frame capability used as backing memory for the structure
699  *
700  * \return SYS_ERR_OK on success
701  *         errno      on failure
702  */
703 errval_t vring_init_from_cap(struct vring *vr,
704                              uint16_t num,
705                              uintptr_t align,
706                              struct capref cap)
707 {
708     errval_t err;
709
710     /* num must be a power of two */
711     assert(((num != 0) && ((num & (~num + 1)) == num)));
712
713     size_t size = vring_size(num, align);
714
715     struct frame_identity id;
716     err = frame_identify(cap, &id);
717     if (err_is_fail(err)) {
718         return err_push(err, LIB_ERR_FRAME_IDENTIFY);
719     }
720
721     /* check if we have enough space in the given cap */
722     if (id.bytes < size) {
723         return SYS_ERR_INVALID_SIZE_BITS;
724     }
725
726     void *addr;
727     err = vspace_map_one_frame(&addr, id.bytes, cap, NULL, NULL);
728     if (err_is_fail(err)) {
729         return err_push(err, LIB_ERR_VSPACE_MAP);
730     }
731
732     vring_init(vr, num, align, addr);
733
734     return SYS_ERR_OK;
735 }
736
737 /**
738  * \brief allocates a new vring structure
739  *
740  * \param vr        pointer to the vring structure
741  * \param num       the number of queue elements
742  * \param align     the alignment constraints for the vring
743  * \param ret_frame returned frame capability
744  *
745  * \return SYS_ERR_OK on success
746  *         errno      on failure
747  */
748 errval_t vring_alloc(struct vring *vr,
749                      uint16_t num,
750                      uintptr_t align,
751                      struct capref *ret_frame)
752 {
753     errval_t err;
754
755     /* num must be a power of two */
756     assert(((num != 0) && ((num & (~num + 1)) == num)));
757
758     size_t size = vring_size(num, align);
759
760     struct capref frame;
761     err = frame_alloc(&frame, size, &size);
762     if (err_is_fail(err)) {
763         return err;
764     }
765
766     err = vring_init_from_cap(vr, num, align, frame);
767     if (err_is_fail(err)) {
768         return err;
769     }
770
771     if (ret_frame) {
772         *ret_frame = frame;
773     }
774
775     return SYS_ERR_OK;
776 }
777
778 /**
779  * \brief frees the resources used by the vring structure
780  *
781  * \param vr the vring to be freed
782  *
783  * \return SYS_ERR_OK on success
784  *         errno      on failure
785  */
786 errval_t vring_free(struct vring *vr)
787 {
788     errval_t err;
789
790     err = vspace_unmap(vr->desc);
791     if (err_is_fail(err)) {
792         return err;
793     }
794
795     assert(!"NYI: returning the cap to the origin");
796     return SYS_ERR_OK;
797 }
798
799 /*
800  * ----------------------------------------------------------------------------
801  *  Queue Management
802  */
803
804 /**
805  * \brief updates the available ring of the virtqueue by placing the descriptor
806  *        into the availabe ring.
807  *
808  * \param vq    the virtqueue to update
809  * \param idx   index of the new descriptor chain head
810  */
811 static void virtqueue_update_available(struct virtqueue *vq,
812                                        uint16_t idx)
813 {
814     uint16_t avail_idx = vq->vring.avail->idx & (vq->desc_num - 1);
815     vq->vring.avail->ring[avail_idx] = idx;
816
817     /*
818      * wmb();
819      */
820
821     VIRTIO_DEBUG_VQ("VQ(%u) avail index = %u, num_queued = %u\n",
822                     vq->queue_index, vq->vring.avail->idx + 1, vq->desc_num_queued + 1);
823
824     vq->vring.avail->idx++;
825     vq->desc_num_queued++;
826 }
827
828 /**
829  * \brief Performs the actual insertion and queue setup of the given buffer list
830  *
831  * \param vq        virtqueue to insert in
832  * \param head      index of the head of the free queue
833  * \param bl        buffer list to be enqueued
834  * \param num_read  number of readable buffers
835  * \param num_write number of writeable buffers
836  * \param ret_idx   the returned new free head index
837  *
838  * \return SYS_ERR_OK on success
839  *         VIRTIO_ERR_* on failulre
840  */
841 static errval_t virtqueue_enqueue_bufs(struct virtqueue *vq,
842                                        uint16_t head,
843                                        struct virtio_buffer_list *bl,
844                                        uint16_t num_read,
845                                        uint16_t num_write,
846                                        uint16_t *ret_idx)
847 {
848     struct vring_desc *desc = vq->vring.desc;
849     struct virtio_buffer *buf = bl->head;
850     struct vring_desc *cd = desc;
851
852     if (bl->state != VIRTIO_BUFFER_LIST_S_FILLED) {
853         return VIRTIO_ERR_BUFFER_STATE;
854     }
855
856
857
858     uint16_t needed = num_read + num_write;
859     uint16_t idx = head;
860
861     VIRTIO_DEBUG_VQ("Enqueuing %u buffers to VQ(%u)\n", needed, vq->queue_index);
862
863     for (uint16_t i = 0; i < needed; ++i) {
864         if (buf->state == VIRTIO_BUFFER_S_QUEUED) {
865             /*
866              * XXX: assume here that read only descriptors can be queued multiple
867              *      times, having the same buffer writable enqueued twices, this
868              *      is clearly an error
869              */
870             if (i >= num_read) {
871                 /*
872                  * do a clean up, reverse pointers and revert the fields
873                  */
874                 idx = head;
875                 buf = bl->head;
876                 for (uint16_t j = 0; j < i; ++j) {
877                     /* reset the buffer state */
878                     buf->state = VIRTIO_BUFFER_S_ALLOCED;
879                     vq->vring_di[idx].buf = NULL;
880                     cd = &desc[idx];
881                     cd->addr = buf->paddr;
882                     cd->length = buf->length;
883                     cd->flags = 0;
884
885                     idx = cd->next;
886                     buf = buf->next;
887                 }
888                 return VIRTIO_ERR_BUFFER_USED;
889             }
890         }
891
892         VIRTIO_DEBUG_VQ("  using idx=%u\n", idx);
893
894         vq->vring_di[idx].buf = buf;
895         cd = &desc[idx];
896
897         cd->addr = buf->paddr;
898         cd->length = buf->length;
899         cd->flags = 0;
900
901         if (i < needed - 1) {
902             cd->flags |= VIRTIO_RING_DESC_F_NEXT;
903         }
904         if (i >= num_read) {
905             cd->flags |= VIRTIO_RING_DESC_F_WRITE;
906         }
907         idx = cd->next;
908         buf = buf->next;
909     }
910
911     cd->next = VIRTQUEUE_CHAIN_END;
912
913     bl->state = VIRTIO_BUFFER_LIST_S_ENQUEUED;
914
915     if (ret_idx) {
916         *ret_idx = idx;
917     }
918
919     return SYS_ERR_OK;
920 }
921
922 /**
923  * \brief Enqueues a new descriptor chain into the virtqueue
924  *
925  * \param vq     the virtqueue the descriptor chain gets enqueued in
926  * \param bl     list of buffers to enqueue into the virtqueue
927  * \param st     state associated with this descriptor chain
928  * \param num_wr number of writable descriptors
929  * \param num_rd number of readable descriptors
930  *
931  * \returns SYS_ERR_OK on success
932  *          VIRTIO_ERR_* on failure
933  */
934 errval_t virtio_virtqueue_desc_enqueue(struct virtqueue *vq,
935                                        struct virtio_buffer_list *bl,
936                                        void *st,
937                                        uint16_t num_wr,
938                                        uint16_t num_rd)
939 {
940     errval_t err;
941
942     uint16_t needed = num_rd + num_wr;
943
944     if (needed != bl->length) {
945         return VIRTIO_ERR_SIZE_INVALID;
946     }
947
948     if (vq->free_count < needed) {
949         return VIRTIO_ERR_QUEUE_EMPTY;
950     }
951
952     /*
953      * TODO: check if we should use indirect descriptors or not
954      */
955
956     uint16_t free_head = vq->free_head;
957     debug_printf("enq using info [%u]\n", free_head);
958     struct vring_desc_info *info = &vq->vring_di[free_head];
959
960     info->is_head = 0x1;
961     info->st = st;
962     info->bl = bl;
963
964     uint16_t idx = 0;
965     err = virtqueue_enqueue_bufs(vq, free_head, bl, num_rd, num_wr, &idx);
966     if (err_is_fail(err)) {
967         return err;
968     }
969
970     /* update free values */
971     vq->free_head = idx;
972     vq->free_count -= needed;
973
974     virtqueue_update_available(vq, free_head);
975
976     return SYS_ERR_OK;
977 }
978
979 static errval_t virtqueue_free_desc_chain(struct virtqueue *vq,
980                                           uint16_t desc_idx)
981 {
982     struct vring_desc *desc;
983     struct vring_desc_info *info;
984
985     desc = &vq->vring.desc[desc_idx];
986     info = &vq->vring_di[desc_idx];
987
988     uint16_t ndesc = info->bl->length;
989
990     vq->free_count += ndesc;
991     ndesc--;
992
993     if ((desc->flags & VIRTIO_RING_DESC_F_INDIRECT) == 0) {
994         while (desc->flags & VIRTIO_RING_DESC_F_NEXT) {
995             desc = &vq->vring.desc[desc->next];
996             ndesc--;
997         }
998     }
999
1000     if (ndesc) {
1001         VIRTIO_DEBUG_VQ("ERROR: descriptor chain ended at %u\n", ndesc);
1002         return VIRTIO_ERR_DEQ_CHAIN;
1003     }
1004
1005     /* append it to the free list of descriptors */
1006     desc->next = vq->free_head;
1007     vq->free_head = desc_idx;
1008
1009     return SYS_ERR_OK;
1010 }
1011
1012 /**
1013  * \brief dequeues a descriptor chain form the virtqueue
1014  *
1015  * \param vq     the virtqueue to dequeue descriptors from
1016  * \param ret_bl returns the associated buffer list structure
1017  * \param ret_st returns the associated state of the queue list
1018  *
1019  * \returns SYS_ERR_OK when the dequeue is successful
1020  *          VIRTIO_ERR_NO_DESC_AVAIL when there was no descriptor to dequeue
1021  *          VIRTIO_ERR_* if there was an error
1022  */
1023 errval_t virtio_virtqueue_desc_dequeue(struct virtqueue *vq,
1024                                        struct virtio_buffer_list **ret_bl,
1025                                        void **ret_st)
1026 {
1027     errval_t err;
1028
1029     struct vring_used_elem *elem;
1030
1031     uint16_t used_idx, desc_idx;
1032
1033     /*
1034      * check if there is a descriptor available
1035      */
1036     if (vq->used_tail == vq->vring.used->idx) {
1037         return VIRTIO_ERR_NO_DESC_AVAIL;
1038     }
1039
1040     used_idx = vq->used_tail++ & (vq->desc_num - 1);
1041     elem = &vq->vring.used->ring[used_idx];
1042
1043     VIRTIO_DEBUG_VQ("Dequeuing element [%u] on the used ring: [%u, %u]\n",
1044                         used_idx, elem->id, elem->length);
1045
1046     /*
1047      * TODO: read memory barrier
1048      * rmb();
1049      * */
1050     desc_idx = (uint16_t) elem->id;
1051
1052     /* get the descritpor information */
1053     struct vring_desc_info *info = &vq->vring_di[desc_idx];
1054     debug_printf("deq using info [%u]\n", desc_idx);
1055
1056     assert(info->is_head);
1057     assert(info->bl);
1058
1059     struct virtio_buffer_list *bl = info->bl;
1060
1061     err = virtqueue_free_desc_chain(vq, desc_idx);
1062     if (err_is_fail(err)) {
1063         used_idx = vq->used_tail-- & (vq->desc_num - 1);
1064         return err;
1065     }
1066
1067     bl->state = VIRTIO_BUFFER_LIST_S_FILLED;
1068
1069     if (ret_bl) {
1070         *ret_bl = bl;
1071     }
1072
1073     if (ret_st) {
1074         *ret_st = info->st;
1075     }
1076
1077     return SYS_ERR_OK;
1078 }
1079
1080 /**
1081  * \brief polls the virtqueue
1082  *
1083  * \param vq         the virtqueue to dequeue descriptors from
1084  * \param ret_bl     returns the associated buffer list structure
1085  * \param ret_st     returns the associated state of the queue list
1086  * \param handle_msg flag to have messages handled
1087  *
1088  * \returns SYS_ERR_OK when the dequeue is successful
1089  *          VIRTIO_ERR_* if there was an error
1090  */
1091 errval_t virtio_virtqueue_poll(struct virtqueue *vq,
1092                                struct virtio_buffer_list **ret_bl,
1093                                void **ret_st,
1094                                uint8_t handle_msg)
1095 {
1096     errval_t err;
1097
1098     err = virtio_virtqueue_desc_dequeue(vq, ret_bl, ret_st);
1099
1100     while (err_no(err) == VIRTIO_ERR_NO_DESC_AVAIL) {
1101         if (handle_msg) {
1102             err = event_dispatch_non_block(get_default_waitset());
1103             if (err_is_fail(err)) {
1104                 if (err_no(err) == LIB_ERR_NO_EVENT) {
1105                     thread_yield();
1106                 }
1107             }
1108         } else {
1109             thread_yield();
1110         }
1111         err = virtio_virtqueue_desc_dequeue(vq, ret_bl, ret_st);
1112     }
1113
1114     return err;
1115 }
1116
1117
1118 /**
1119  * \brief returns a buffer allocator based on the buffers with the virtqueue
1120  *        (if any)
1121  *
1122  * \param vq the virtqueue to get the buffer allocator
1123  * \param alloc returns the pointer to the allocator
1124  *
1125  * \returns SYS_ERR_OK on SUCCESS
1126  *          VIRTIO_ERR_BUFFER_SIZE if there are no buffers allocated
1127  */
1128 errval_t virtio_virtqueue_get_buf_alloc(struct virtqueue *vq,
1129                                         struct virtio_buffer_allocator **alloc)
1130 {
1131     assert(alloc);
1132
1133     if (vq->buffer_bits) {
1134         if (vq->buffer_alloc != NULL) {
1135             *alloc = vq->buffer_alloc;
1136             return SYS_ERR_OK;
1137         }
1138         // XXX: this is actually an error and should not happen
1139         return VIRTIO_ERR_NO_BUFFER;
1140     }
1141
1142     return VIRTIO_ERR_NO_BUFFER;
1143 }