L4Re - L4 Runtime Environment
virtqueue
1 // vi:ft=cpp
2 /*
3  * (c) 2014 Alexander Warg <warg@os.inf.tu-dresden.de>
4  *
5  * This file is part of TUD:OS and distributed under the terms of the
6  * GNU General Public License 2.
7  * Please see the COPYING-GPL-2 file for details.
8  *
9  * As a special exception, you may use this file as part of a free software
10  * library without restriction. Specifically, if other files instantiate
11  * templates or use macros or inline functions from this file, or you compile
12  * this file and link it with other files to produce an executable, this
13  * file does not by itself cause the resulting executable to be covered by
14  * the GNU General Public License. This exception does not however
15  * invalidate any other reasons why the executable file might be covered by
16  * the GNU General Public License.
17  */
18 
19 #include <l4/re/util/debug>
20 #include <l4/sys/types.h>
21 #include <l4/sys/err.h>
22 #include <l4/cxx/bitfield>
23 #include <l4/cxx/exceptions>
24 #include <cstdint>
25 
26 #pragma once
27 
28 namespace L4virtio {
29 
30 #ifdef __ARM_ARCH_7A__
31 static inline void wmb() { asm volatile ("dmb" : : : "memory"); }
32 static inline void rmb() { asm volatile ("dmb" : : : "memory"); }
33 #elif defined(__ARM_ARCH_8A)
34 static inline void wmb() { asm volatile ("dsb ishst" : : : "memory"); }
35 static inline void rmb() { asm volatile ("dsb ishld" : : : "memory"); }
36 #elif defined(__mips__)
37 static inline void wmb() { asm volatile ("sync" : : : "memory"); }
38 static inline void rmb() { asm volatile ("sync" : : : "memory"); }
39 #elif defined(__amd64__) || defined (__i686__)
40 static inline void wmb() { asm volatile ("sfence" : : : "memory"); }
41 static inline void rmb() { asm volatile ("lfence" : : : "memory"); }
42 #else
43 #warning Missing proper memory write barrier
44 static inline void wmb() { asm volatile ("" : : : "memory"); }
45 static inline void rmb() { asm volatile ("" : : : "memory"); }
46 #endif
47 
48 
49 /**
50  * Pointer used in virtio descriptors.
51  *
52  * As the descriptor contain guest addresses these pointers cannot be
53  * dereferenced directly.
54  */
55 template< typename T >
56 class Ptr
57 {
58 public:
59  /// Type for making an invalid (NULL) Ptr.
60  enum Invalid_type { Invalid /**< Use to set a Ptr to invalid (NULL) */ };
61 
62  Ptr() = default;
63 
64  /// Make and invalid Ptr
65  Ptr(Invalid_type) : _p(~0ULL) {}
66 
67  /// Make a Ptr from a raw 64bit address
68  explicit Ptr(l4_uint64_t vm_addr) : _p(vm_addr) {}
69 
70  /// \return The raw 64bit address of the pointer.
71  l4_uint64_t get() const { return _p; }
72 
73  /// \return true if the pointer is invalid (NULL).
74  bool is_valid() const { return _p != ~0ULL; }
75 
76 private:
77  l4_uint64_t _p;
78 };
79 
80 
81 /**
82  * Low-level Virtqueue.
83  *
84  * This class represents a single virtqueue, with a local running available
85  * index.
86  */
87 class Virtqueue
88 {
89 public:
90  /**
91  * Descriptor in the descriptor table.
92  */
93  class Desc
94  {
95  public:
96  /**
97  * Type for descriptor flags.
98  */
99  struct Flags
100  {
101  l4_uint16_t raw; ///< raw flags value of a virtio descriptor.
102  Flags() = default;
103 
104  /// Make Flags from raw 16bit value.
105  explicit Flags(l4_uint16_t v) : raw(v) {}
106 
107  /// Part of a descriptor chain which is continued with the next field.
108  CXX_BITFIELD_MEMBER( 0, 0, next, raw);
109  /// Block described by this descriptor is writeable.
110  CXX_BITFIELD_MEMBER( 1, 1, write, raw);
111  /// Indirect descriptor, block contains a list of descriptors.
112  CXX_BITFIELD_MEMBER( 2, 2, indirect, raw);
113  };
114 
115  Ptr<void> addr; ///< Address stored in descriptor.
116  l4_uint32_t len; ///< Length of described buffer.
117  Flags flags; ///< Descriptor flags.
118  l4_uint16_t next; ///< Index of the next chained descriptor.
119 
120  /**
121  * Dump a single descriptor.
122  */
123  void dump(unsigned idx) const
124  {
125  L4Re::Util::Dbg().printf("D[%04x]: %08llx (%x) f=%04x n=%04x\n",
126  idx, addr.get(),
127  len, (unsigned)flags.raw, (unsigned)next);
128  }
129  };
130 
131  /**
132  * Type of available ring, this is read-only for the host.
133  */
134  class Avail
135  {
136  public:
137  /**
138  * Flags of the available ring.
139  */
140  struct Flags
141  {
142  l4_uint16_t raw; ///< raw 16bit flags value of the available ring.
143  Flags() = default;
144 
145  /// Make Flags from the raw value.
146  explicit Flags(l4_uint16_t v) : raw(v) {}
147 
148  /// Guest does not want to receive interrupts when requests are finished.
149  CXX_BITFIELD_MEMBER( 0, 0, no_irq, raw);
150  };
151 
152  Flags flags; ///< flags of available ring
153  l4_uint16_t idx; ///< available index written by guest
154  l4_uint16_t ring[]; ///< array of available descriptor indexes.
155  };
156 
157  /**
158  * Type of an element of the used ring.
159  */
160  struct Used_elem
161  {
162  Used_elem() = default;
163 
164  /**
165  * Initialize a used ring element.
166  *
167  * \param id The index of the descriptor to be marked as used.
168  * \param len The total bytes written into the buffer of the
169  * descriptor chain.
170  */
171  Used_elem(l4_uint16_t id, l4_uint32_t len) : id(id), len(len) {}
172  l4_uint32_t id; ///< descriptor index
173  l4_uint32_t len; ///< length field
174  };
175 
176  /**
177  * Used ring.
178  */
179  class Used
180  {
181  public:
182  /**
183  * flags for the used ring.
184  */
185  struct Flags
186  {
187  l4_uint16_t raw; ///< raw flags value as specified by virtio.
188  Flags() = default;
189 
190  /// make Flags from raw value
191  explicit Flags(l4_uint16_t v) : raw(v) {}
192 
193  /// host does not want to be notified when new requests have been queued.
194  CXX_BITFIELD_MEMBER( 0, 0, no_notify, raw);
195  };
196 
197  Flags flags; ///< flags of the used ring.
198  l4_uint16_t idx; ///< index of the last entry in the ring.
199  Used_elem ring[]; ///< array of used descriptors.
200  };
201 
202 protected:
203  Desc *_desc; ///< pointer to descriptor table, NULL if queue is off.
204  Avail *_avail; ///< pointer to available ring.
205  Used *_used; ///< pointer to used ring.
206 
207  /** The life counter for the queue */
208  l4_uint16_t _current_avail;
209 
210  /**
211  * mask used for indexing into the descriptor table
212  * and the rings.
213  */
214  l4_uint16_t _idx_mask;
215 
216  /**
217  * Create a disabled virtqueue.
218  */
219  Virtqueue() : _desc(0), _idx_mask(0) {}
220  Virtqueue(Virtqueue const &) = delete;
221 
222 public:
223  /**
224  * Completely disable the queue.
225  *
226  * setup() must be used to enable the queue again.
227  */
228  void disable()
229  { _desc = 0; }
230 
231  /**
232  * Fixed alignment values for different parts of a virtqueue.
233  */
234  enum
235  {
236  Desc_align = 4, //< Alignment of the descriptor table.
237  Avail_align = 1, //< Alignment of the available ring.
238  Used_align = 2, //< Alignment of the used ring.
239  };
240 
241  /**
242  * Calculate the total size for a virtqueue of the given dimensions.
243  *
244  * \param num The number of entries in the descriptor table, the
245  * available ring, and the used ring (must be a power of 2).
246  *
247  * \return The total size in bytes of the queue data structures.
248  */
249  static unsigned long total_size(unsigned num)
250  {
251  static_assert(Desc_align >= Avail_align,
252  "virtqueue alignment assumptions broken");
253  return l4_round_size(desc_size(num) + avail_size(num), Used_align)
254  + used_size(num);
255  }
256 
257  /**
258  * Calculate the size of the descriptor table for `num` entries.
259  *
260  * \param num The number of entries in the descriptor table.
261  *
262  * \returns The size in bytes needed for a descriptor table with
263  * `num` entries.
264  */
265  static unsigned long desc_size(unsigned num)
266  { return num * 16; }
267 
268  /**
269  * Get the alignment in zero LSBs needed for the descriptor table.
270  *
271  * \returns The alignment in zero LSBs needed for a descriptor table.
272  */
273  static unsigned long desc_align()
274  { return Desc_align; }
275 
276  /**
277  * Calculate the size of the available ring for `num` entries.
278  *
279  * \param num The number of entries in the available ring.
280  * \returns The size in bytes needed for an available ring with
281  * `num` entries.
282  */
283  static unsigned long avail_size(unsigned num)
284  { return 2 * num + 6; }
285 
286  /**
287  * Get the alignment in zero LSBs needed for the available ring.
288  *
289  * \returns The alignment in zero LSBs needed for an available ring.
290  */
291  static unsigned long avail_align()
292  { return Avail_align; }
293 
294  /**
295  * Calculate the size of the used ring for `num` entries.
296  *
297  * \param num The number of entries in the used ring.
298  *
299  * \returns The size in bytes needed for an used ring with
300  * `num` entries.
301  */
302  static unsigned long used_size(unsigned num)
303  { return 8 * num + 6; }
304 
305  /**
306  * Get the alignment in zero LSBs needed for the used ring.
307  *
308  * \returns The alignment in zero LSBs needed for an used ring.
309  */
310  static unsigned long used_align()
311  { return Used_align; }
312 
313  /**
314  * Calculate the total size of this virtqueue.
315  *
316  * \pre The queue has been set up.
317  */
318  unsigned long total_size() const
319  {
320  return ((char *) _used - (char *) _desc)
321  + used_size(num());
322  }
323 
324  /**
325  * Get the offset of the available ring from the descriptor table.
326  */
327  unsigned long avail_offset() const
328  { return (char const *)_avail - (char const *)_desc; }
329 
330  /**
331  * Get the offset of the used ring from the descriptor table.
332  */
333  unsigned long used_offset() const
334  { return (char const *)_used - (char const *)_desc; }
335 
336  /**
337  * Enable this queue.
338  *
339  * \param num The number of entries in the descriptor table, the
340  * available ring, and the used ring (must be a power of 2).
341  * \param desc The address of the descriptor table. (Must be
342  * Desc_align aligned and at least `desc_size(num)` bytes
343  * in size.)
344  * \param avail The address of the available ring. (Must be
345  * Avail_align aligned and at least `avail_size(num)` bytes
346  * in size.)
347  * \param used The address of the used ring. (Must be Used_align aligned
348  * and at least `used_size(num)` bytes in size.)
349  *
350  * Due to the data type of the descriptors, the queue can have a
351  * maximum size of 2^16.
352  */
353  void setup(unsigned num, void *desc, void *avail, void *used)
354  {
355  if (num > 0x10000)
356  throw L4::Runtime_error(-L4_EINVAL, "Queue too large.");
357 
358  _idx_mask = num - 1;
359  _desc = (Desc*)desc;
360  _avail = (Avail*)avail;
361  _used = (Used*)used;
362 
363  _current_avail = 0;
364 
365  L4Re::Util::Dbg().printf("VQ[%p]: num=%d d:%p a:%p u:%p\n",
366  this, num, _desc, _avail, _used);
367  }
368 
369  /**
370  * Enable this queue.
371  *
372  * \param num The number of entries in the descriptor table, the
373  * available ring, and the used ring (must be a power of 2).
374  * \param ring The base address for the queue data structure. The memory
375  * block at `ring` must be at least `total_size(num)` bytes
376  * in size and have an alignment of Desc_align
377  * (desc_align()) bits.
378  *
379  * Due to the data type of the descriptors, the queue can have a
380  * maximum size of 2^16.
381  */
382  void setup_simple(unsigned num, void *ring)
383  {
384  l4_addr_t desc = reinterpret_cast<l4_addr_t>(ring);
385  l4_addr_t avail = l4_round_size(desc + desc_size(num), Avail_align);
386  l4_addr_t used = l4_round_size(avail + avail_size(num), Used_align);
387  setup(num, (void *)desc, (void *)avail, (void *)used);
388  }
389 
390  /**
391  * Dump descriptors for this queue.
392  *
393  * \pre the queue must be in working state.
394  */
395  void dump(Desc const *d) const
396  { d->dump(d - _desc); }
397 
398  /**
399  * Test if this queue is in working state.
400  *
401  * \return true when the queue is in working state, false else.
402  */
403  bool ready() const
404  { return L4_LIKELY(_desc != 0); }
405 
406  /// \return The number of entries in the ring.
407  unsigned num() const
408  { return _idx_mask + 1; }
409 
410  /**
411  * Get the no IRQ flag of this queue.
412  *
413  * \pre queue must be in working state.
414  *
415  * \return true if the guest does not want to get IRQs (currently).
416  */
417  bool no_notify_guest() const
418  {
419  return _avail->flags.no_irq();
420  }
421 
422  /**
423  * Get the no notify flag of this queue.
424  *
425  * \pre queue must be in working state.
426  *
427  * \return true if the host does not want to get IRQs (currently).
428  */
429  bool no_notify_host() const
430  {
431  return _used->flags.no_notify();
432  }
433 
434  /**
435  * Set the no-notify flag for this queue
436  *
437  * \pre Queue must be in a working state.
438  */
439  void no_notify_host(bool value)
440  {
441  _used->flags.no_notify() = value;
442  }
443 
444  /**
445  * Get available index from available ring (for debugging).
446  *
447  * \pre Queue must be in a working state.
448  *
449  * \return current index in the available ring (shared
450  * between device model and device driver).
451  */
452  l4_uint16_t get_avail_idx() const { return _avail->idx; }
453 
454  /**
455  * Get tail-available index stored in local state (for debugging).
456  *
457  * \return current tail index for the the available ring.
458  */
459  l4_uint16_t get_tail_avail_idx() const { return _current_avail; }
460 
461 };
462 
463 namespace Driver {
464 
465 /**
466  * Driver-side implementation of a Virtqueue.
467  *
468  * Adds function for managing the descriptor list, enqueueing new
469  * and dequeueing finished requests.
470  */
471 class Virtqueue : public L4virtio::Virtqueue
472 {
473 private:
474  /// Index of next free entry in the descriptor table.
475  l4_uint16_t _next_free;
476 
477 public:
478  enum End_of_queue
479  {
480  // Indicates the end of the queue.
481  Eoq = 0xFFFF
482  };
483 
484  Virtqueue() : _next_free(Eoq) {}
485 
486  /**
487  * Initialize the descriptor table and the index structures
488  * of this queue.
489  *
490  * \param num The number of entries in the descriptor table, the
491  * available ring, and the used ring (must be a power of 2).
492  *
493  * \pre The queue must be set up correctly with setup() or setup_simple().
494  */
495  void initialize_rings(unsigned num)
496  {
497  _used->idx = 0;
498  _avail->idx = 0;
499 
500  // setup the freelist
501  for (l4_uint16_t d = 0; d < num - 1; ++d)
502  _desc[d].next = d + 1;
503  _desc[num - 1].next = Eoq;
504  _next_free = 0;
505  }
506 
507  /**
508  * Initialize this virtqueue.
509  *
510  * \param num The number of entries in the descriptor table, the
511  * available ring, and the used ring (must be a power of 2).
512  * \param desc The address of the descriptor table. (Must be
513  * Desc_align aligned and at least `desc_size(num)` bytes
514  * in size.)
515  * \param avail The address of the available ring. (Must be
516  * Avail_align aligned and at least `avail_size(num)` bytes
517  * in size.)
518  * \param used The address of the used ring. (Must be Used_align aligned
519  * and at least `used_size(num)` bytes in size.)
520  *
521  * This function sets up the memory and initializes the freelist.
522  */
523  void init_queue(unsigned num, void *desc, void *avail, void *used)
524  {
525  setup(num, desc, avail, used);
526  initialize_rings(num);
527  }
528 
529  /**
530  * Initialize this virtqueue.
531  *
532  * \param num The number of entries in the descriptor table, the
533  * available ring, and the used ring (must be a power of 2).
534  * \param base The base address for the queue data structure.
535  *
536  * This function sets up the memory and initializes the freelist.
537  */
538  void init_queue(unsigned num, void *base)
539  {
540  setup_simple(num, base);
541  initialize_rings(num);
542  }
543 
544 
545  /**
546  * Allocate and return an unused descriptor from the descriptor table.
547  *
548  * The descriptor will be removed from the free list, the content
549  * should be considered undefined. After use, it needs to be freed
550  * using free_descriptor().
551  *
552  * \return The index of the reserved descriptor or Virtqueue::Eoq if
553  * no free descriptor is available.
554  *
555  * Note: the implementation uses (2^16 - 1) as the end of queue marker.
556  * That means that the final entry in the queue can not be allocated
557  * iff the queue size is 2^16.
558  */
559  l4_uint16_t alloc_descriptor()
560  {
561  // XXX needs to be locked
562  l4_uint16_t idx = _next_free;
563  if (idx == Eoq)
564  return Eoq;
565 
566  _next_free = _desc[idx].next;
567 
568  return idx;
569  }
570 
571  /**
572  * Enqueue a descriptor in the available ring.
573  *
574  * \param descno Index of the head descriptor to enqueue.
575  */
576  void enqueue_descriptor(l4_uint16_t descno)
577  {
578  if (descno > _idx_mask)
579  throw L4::Bounds_error();
580 
581  // TODO lock required
582  _avail->ring[_avail->idx & _idx_mask] = descno; // _avail->idx expected to wrap
583  wmb();
584  ++_avail->idx;
585  }
586 
587  /**
588  * Return a reference to a descriptor in the descriptor table.
589  *
590  * \param descno Index of the descriptor,
591  * expected to be in correct range.
592  */
593  Desc &desc(l4_uint16_t descno)
594  {
595  if (descno > _idx_mask)
596  throw L4::Bounds_error();
597 
598  return _desc[descno];
599  }
600 
601  /**
602  * Return the next finished block.
603  *
604  * \param[out] len (optional) Size of valid data in finished block.
605  * Note that this is the value reported by the device,
606  * which may set it to a value that is larger than the
607  * original buffer size.
608  *
609  * \return Index of the head or Virtqueue::Eoq
610  * if no used element is currently available.
611  */
612  l4_uint16_t find_next_used(l4_uint32_t *len = nullptr)
613  {
614  // TODO lock required
615  if (_current_avail == _used->idx)
616  return Eoq;
617 
618  auto elem = _used->ring[_current_avail++ & _idx_mask];
619 
620  if (len)
621  *len = elem.len;
622 
623  return elem.id;
624  }
625 
626  /**
627  * Free a chained list of descriptors in the descriptor queue.
628  *
629  * \param head Index of the first element in the descriptor chain.
630  * \param tail Index of the last element in the descriptor chain.
631  *
632  * Simply takes the descriptor chain and prepends it to the beginning
633  * of the free list. Assumes that the list has been correctly chained.
634  */
635  void free_descriptor(l4_uint16_t head, l4_uint16_t tail)
636  {
637  if (head > _idx_mask || tail > _idx_mask)
638  throw L4::Bounds_error();
639 
640  // TODO lock required
641  _desc[tail].next = _next_free;
642  _next_free = head;
643  }
644 };
645 
646 }
647 } // namespace L4virtio