vhost: export API to translate gpa to vva
[dpdk.git] / lib / librte_vhost / virtio_net.c
1 /*-
2  *   BSD LICENSE
3  *
4  *   Copyright(c) 2010-2016 Intel Corporation. All rights reserved.
5  *   All rights reserved.
6  *
7  *   Redistribution and use in source and binary forms, with or without
8  *   modification, are permitted provided that the following conditions
9  *   are met:
10  *
11  *     * Redistributions of source code must retain the above copyright
12  *       notice, this list of conditions and the following disclaimer.
13  *     * Redistributions in binary form must reproduce the above copyright
14  *       notice, this list of conditions and the following disclaimer in
15  *       the documentation and/or other materials provided with the
16  *       distribution.
17  *     * Neither the name of Intel Corporation nor the names of its
18  *       contributors may be used to endorse or promote products derived
19  *       from this software without specific prior written permission.
20  *
21  *   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22  *   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23  *   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24  *   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25  *   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26  *   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
27  *   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
28  *   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
29  *   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
30  *   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
31  *   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32  */
33
34 #include <stdint.h>
35 #include <stdbool.h>
36 #include <linux/virtio_net.h>
37
38 #include <rte_mbuf.h>
39 #include <rte_memcpy.h>
40 #include <rte_ether.h>
41 #include <rte_ip.h>
42 #include <rte_virtio_net.h>
43 #include <rte_tcp.h>
44 #include <rte_udp.h>
45 #include <rte_sctp.h>
46 #include <rte_arp.h>
47
48 #include "vhost.h"
49
50 #define MAX_PKT_BURST 32
51 #define VHOST_LOG_PAGE  4096
52
53 static inline void __attribute__((always_inline))
54 vhost_log_page(uint8_t *log_base, uint64_t page)
55 {
56         log_base[page / 8] |= 1 << (page % 8);
57 }
58
59 static inline void __attribute__((always_inline))
60 vhost_log_write(struct virtio_net *dev, uint64_t addr, uint64_t len)
61 {
62         uint64_t page;
63
64         if (likely(((dev->features & (1ULL << VHOST_F_LOG_ALL)) == 0) ||
65                    !dev->log_base || !len))
66                 return;
67
68         if (unlikely(dev->log_size <= ((addr + len - 1) / VHOST_LOG_PAGE / 8)))
69                 return;
70
71         /* To make sure guest memory updates are committed before logging */
72         rte_smp_wmb();
73
74         page = addr / VHOST_LOG_PAGE;
75         while (page * VHOST_LOG_PAGE < addr + len) {
76                 vhost_log_page((uint8_t *)(uintptr_t)dev->log_base, page);
77                 page += 1;
78         }
79 }
80
81 static inline void __attribute__((always_inline))
82 vhost_log_used_vring(struct virtio_net *dev, struct vhost_virtqueue *vq,
83                      uint64_t offset, uint64_t len)
84 {
85         vhost_log_write(dev, vq->log_guest_addr + offset, len);
86 }
87
88 static bool
89 is_valid_virt_queue_idx(uint32_t idx, int is_tx, uint32_t qp_nb)
90 {
91         return (is_tx ^ (idx & 1)) == 0 && idx < qp_nb * VIRTIO_QNUM;
92 }
93
94 static inline void __attribute__((always_inline))
95 do_flush_shadow_used_ring(struct virtio_net *dev, struct vhost_virtqueue *vq,
96                           uint16_t to, uint16_t from, uint16_t size)
97 {
98         rte_memcpy(&vq->used->ring[to],
99                         &vq->shadow_used_ring[from],
100                         size * sizeof(struct vring_used_elem));
101         vhost_log_used_vring(dev, vq,
102                         offsetof(struct vring_used, ring[to]),
103                         size * sizeof(struct vring_used_elem));
104 }
105
106 static inline void __attribute__((always_inline))
107 flush_shadow_used_ring(struct virtio_net *dev, struct vhost_virtqueue *vq)
108 {
109         uint16_t used_idx = vq->last_used_idx & (vq->size - 1);
110
111         if (used_idx + vq->shadow_used_idx <= vq->size) {
112                 do_flush_shadow_used_ring(dev, vq, used_idx, 0,
113                                           vq->shadow_used_idx);
114         } else {
115                 uint16_t size;
116
117                 /* update used ring interval [used_idx, vq->size] */
118                 size = vq->size - used_idx;
119                 do_flush_shadow_used_ring(dev, vq, used_idx, 0, size);
120
121                 /* update the left half used ring interval [0, left_size] */
122                 do_flush_shadow_used_ring(dev, vq, 0, size,
123                                           vq->shadow_used_idx - size);
124         }
125         vq->last_used_idx += vq->shadow_used_idx;
126
127         rte_smp_wmb();
128
129         *(volatile uint16_t *)&vq->used->idx += vq->shadow_used_idx;
130         vhost_log_used_vring(dev, vq, offsetof(struct vring_used, idx),
131                 sizeof(vq->used->idx));
132 }
133
134 static inline void __attribute__((always_inline))
135 update_shadow_used_ring(struct vhost_virtqueue *vq,
136                          uint16_t desc_idx, uint16_t len)
137 {
138         uint16_t i = vq->shadow_used_idx++;
139
140         vq->shadow_used_ring[i].id  = desc_idx;
141         vq->shadow_used_ring[i].len = len;
142 }
143
144 static void
145 virtio_enqueue_offload(struct rte_mbuf *m_buf, struct virtio_net_hdr *net_hdr)
146 {
147         if (m_buf->ol_flags & PKT_TX_L4_MASK) {
148                 net_hdr->flags = VIRTIO_NET_HDR_F_NEEDS_CSUM;
149                 net_hdr->csum_start = m_buf->l2_len + m_buf->l3_len;
150
151                 switch (m_buf->ol_flags & PKT_TX_L4_MASK) {
152                 case PKT_TX_TCP_CKSUM:
153                         net_hdr->csum_offset = (offsetof(struct tcp_hdr,
154                                                 cksum));
155                         break;
156                 case PKT_TX_UDP_CKSUM:
157                         net_hdr->csum_offset = (offsetof(struct udp_hdr,
158                                                 dgram_cksum));
159                         break;
160                 case PKT_TX_SCTP_CKSUM:
161                         net_hdr->csum_offset = (offsetof(struct sctp_hdr,
162                                                 cksum));
163                         break;
164                 }
165         }
166
167         if (m_buf->ol_flags & PKT_TX_TCP_SEG) {
168                 if (m_buf->ol_flags & PKT_TX_IPV4)
169                         net_hdr->gso_type = VIRTIO_NET_HDR_GSO_TCPV4;
170                 else
171                         net_hdr->gso_type = VIRTIO_NET_HDR_GSO_TCPV6;
172                 net_hdr->gso_size = m_buf->tso_segsz;
173                 net_hdr->hdr_len = m_buf->l2_len + m_buf->l3_len
174                                         + m_buf->l4_len;
175         }
176 }
177
178 static inline void
179 copy_virtio_net_hdr(struct virtio_net *dev, uint64_t desc_addr,
180                     struct virtio_net_hdr_mrg_rxbuf hdr)
181 {
182         if (dev->vhost_hlen == sizeof(struct virtio_net_hdr_mrg_rxbuf))
183                 *(struct virtio_net_hdr_mrg_rxbuf *)(uintptr_t)desc_addr = hdr;
184         else
185                 *(struct virtio_net_hdr *)(uintptr_t)desc_addr = hdr.hdr;
186 }
187
188 static inline int __attribute__((always_inline))
189 copy_mbuf_to_desc(struct virtio_net *dev, struct vring_desc *descs,
190                   struct rte_mbuf *m, uint16_t desc_idx, uint32_t size)
191 {
192         uint32_t desc_avail, desc_offset;
193         uint32_t mbuf_avail, mbuf_offset;
194         uint32_t cpy_len;
195         struct vring_desc *desc;
196         uint64_t desc_addr;
197         struct virtio_net_hdr_mrg_rxbuf virtio_hdr = {{0, 0, 0, 0, 0, 0}, 0};
198         /* A counter to avoid desc dead loop chain */
199         uint16_t nr_desc = 1;
200
201         desc = &descs[desc_idx];
202         desc_addr = rte_vhost_gpa_to_vva(dev->mem, desc->addr);
203         /*
204          * Checking of 'desc_addr' placed outside of 'unlikely' macro to avoid
205          * performance issue with some versions of gcc (4.8.4 and 5.3.0) which
206          * otherwise stores offset on the stack instead of in a register.
207          */
208         if (unlikely(desc->len < dev->vhost_hlen) || !desc_addr)
209                 return -1;
210
211         rte_prefetch0((void *)(uintptr_t)desc_addr);
212
213         virtio_enqueue_offload(m, &virtio_hdr.hdr);
214         copy_virtio_net_hdr(dev, desc_addr, virtio_hdr);
215         vhost_log_write(dev, desc->addr, dev->vhost_hlen);
216         PRINT_PACKET(dev, (uintptr_t)desc_addr, dev->vhost_hlen, 0);
217
218         desc_offset = dev->vhost_hlen;
219         desc_avail  = desc->len - dev->vhost_hlen;
220
221         mbuf_avail  = rte_pktmbuf_data_len(m);
222         mbuf_offset = 0;
223         while (mbuf_avail != 0 || m->next != NULL) {
224                 /* done with current mbuf, fetch next */
225                 if (mbuf_avail == 0) {
226                         m = m->next;
227
228                         mbuf_offset = 0;
229                         mbuf_avail  = rte_pktmbuf_data_len(m);
230                 }
231
232                 /* done with current desc buf, fetch next */
233                 if (desc_avail == 0) {
234                         if ((desc->flags & VRING_DESC_F_NEXT) == 0) {
235                                 /* Room in vring buffer is not enough */
236                                 return -1;
237                         }
238                         if (unlikely(desc->next >= size || ++nr_desc > size))
239                                 return -1;
240
241                         desc = &descs[desc->next];
242                         desc_addr = rte_vhost_gpa_to_vva(dev->mem, desc->addr);
243                         if (unlikely(!desc_addr))
244                                 return -1;
245
246                         desc_offset = 0;
247                         desc_avail  = desc->len;
248                 }
249
250                 cpy_len = RTE_MIN(desc_avail, mbuf_avail);
251                 rte_memcpy((void *)((uintptr_t)(desc_addr + desc_offset)),
252                         rte_pktmbuf_mtod_offset(m, void *, mbuf_offset),
253                         cpy_len);
254                 vhost_log_write(dev, desc->addr + desc_offset, cpy_len);
255                 PRINT_PACKET(dev, (uintptr_t)(desc_addr + desc_offset),
256                              cpy_len, 0);
257
258                 mbuf_avail  -= cpy_len;
259                 mbuf_offset += cpy_len;
260                 desc_avail  -= cpy_len;
261                 desc_offset += cpy_len;
262         }
263
264         return 0;
265 }
266
267 /**
268  * This function adds buffers to the virtio devices RX virtqueue. Buffers can
269  * be received from the physical port or from another virtio device. A packet
270  * count is returned to indicate the number of packets that are succesfully
271  * added to the RX queue. This function works when the mbuf is scattered, but
272  * it doesn't support the mergeable feature.
273  */
274 static inline uint32_t __attribute__((always_inline))
275 virtio_dev_rx(struct virtio_net *dev, uint16_t queue_id,
276               struct rte_mbuf **pkts, uint32_t count)
277 {
278         struct vhost_virtqueue *vq;
279         uint16_t avail_idx, free_entries, start_idx;
280         uint16_t desc_indexes[MAX_PKT_BURST];
281         struct vring_desc *descs;
282         uint16_t used_idx;
283         uint32_t i, sz;
284
285         LOG_DEBUG(VHOST_DATA, "(%d) %s\n", dev->vid, __func__);
286         if (unlikely(!is_valid_virt_queue_idx(queue_id, 0, dev->virt_qp_nb))) {
287                 RTE_LOG(ERR, VHOST_DATA, "(%d) %s: invalid virtqueue idx %d.\n",
288                         dev->vid, __func__, queue_id);
289                 return 0;
290         }
291
292         vq = dev->virtqueue[queue_id];
293         if (unlikely(vq->enabled == 0))
294                 return 0;
295
296         avail_idx = *((volatile uint16_t *)&vq->avail->idx);
297         start_idx = vq->last_used_idx;
298         free_entries = avail_idx - start_idx;
299         count = RTE_MIN(count, free_entries);
300         count = RTE_MIN(count, (uint32_t)MAX_PKT_BURST);
301         if (count == 0)
302                 return 0;
303
304         LOG_DEBUG(VHOST_DATA, "(%d) start_idx %d | end_idx %d\n",
305                 dev->vid, start_idx, start_idx + count);
306
307         /* Retrieve all of the desc indexes first to avoid caching issues. */
308         rte_prefetch0(&vq->avail->ring[start_idx & (vq->size - 1)]);
309         for (i = 0; i < count; i++) {
310                 used_idx = (start_idx + i) & (vq->size - 1);
311                 desc_indexes[i] = vq->avail->ring[used_idx];
312                 vq->used->ring[used_idx].id = desc_indexes[i];
313                 vq->used->ring[used_idx].len = pkts[i]->pkt_len +
314                                                dev->vhost_hlen;
315                 vhost_log_used_vring(dev, vq,
316                         offsetof(struct vring_used, ring[used_idx]),
317                         sizeof(vq->used->ring[used_idx]));
318         }
319
320         rte_prefetch0(&vq->desc[desc_indexes[0]]);
321         for (i = 0; i < count; i++) {
322                 uint16_t desc_idx = desc_indexes[i];
323                 int err;
324
325                 if (vq->desc[desc_idx].flags & VRING_DESC_F_INDIRECT) {
326                         descs = (struct vring_desc *)(uintptr_t)
327                                 rte_vhost_gpa_to_vva(dev->mem,
328                                         vq->desc[desc_idx].addr);
329                         if (unlikely(!descs)) {
330                                 count = i;
331                                 break;
332                         }
333
334                         desc_idx = 0;
335                         sz = vq->desc[desc_idx].len / sizeof(*descs);
336                 } else {
337                         descs = vq->desc;
338                         sz = vq->size;
339                 }
340
341                 err = copy_mbuf_to_desc(dev, descs, pkts[i], desc_idx, sz);
342                 if (unlikely(err)) {
343                         used_idx = (start_idx + i) & (vq->size - 1);
344                         vq->used->ring[used_idx].len = dev->vhost_hlen;
345                         vhost_log_used_vring(dev, vq,
346                                 offsetof(struct vring_used, ring[used_idx]),
347                                 sizeof(vq->used->ring[used_idx]));
348                 }
349
350                 if (i + 1 < count)
351                         rte_prefetch0(&vq->desc[desc_indexes[i+1]]);
352         }
353
354         rte_smp_wmb();
355
356         *(volatile uint16_t *)&vq->used->idx += count;
357         vq->last_used_idx += count;
358         vhost_log_used_vring(dev, vq,
359                 offsetof(struct vring_used, idx),
360                 sizeof(vq->used->idx));
361
362         /* flush used->idx update before we read avail->flags. */
363         rte_mb();
364
365         /* Kick the guest if necessary. */
366         if (!(vq->avail->flags & VRING_AVAIL_F_NO_INTERRUPT)
367                         && (vq->callfd >= 0))
368                 eventfd_write(vq->callfd, (eventfd_t)1);
369         return count;
370 }
371
372 static inline int __attribute__((always_inline))
373 fill_vec_buf(struct virtio_net *dev, struct vhost_virtqueue *vq,
374                          uint32_t avail_idx, uint32_t *vec_idx,
375                          struct buf_vector *buf_vec, uint16_t *desc_chain_head,
376                          uint16_t *desc_chain_len)
377 {
378         uint16_t idx = vq->avail->ring[avail_idx & (vq->size - 1)];
379         uint32_t vec_id = *vec_idx;
380         uint32_t len    = 0;
381         struct vring_desc *descs = vq->desc;
382
383         *desc_chain_head = idx;
384
385         if (vq->desc[idx].flags & VRING_DESC_F_INDIRECT) {
386                 descs = (struct vring_desc *)(uintptr_t)
387                         rte_vhost_gpa_to_vva(dev->mem, vq->desc[idx].addr);
388                 if (unlikely(!descs))
389                         return -1;
390
391                 idx = 0;
392         }
393
394         while (1) {
395                 if (unlikely(vec_id >= BUF_VECTOR_MAX || idx >= vq->size))
396                         return -1;
397
398                 len += descs[idx].len;
399                 buf_vec[vec_id].buf_addr = descs[idx].addr;
400                 buf_vec[vec_id].buf_len  = descs[idx].len;
401                 buf_vec[vec_id].desc_idx = idx;
402                 vec_id++;
403
404                 if ((descs[idx].flags & VRING_DESC_F_NEXT) == 0)
405                         break;
406
407                 idx = descs[idx].next;
408         }
409
410         *desc_chain_len = len;
411         *vec_idx = vec_id;
412
413         return 0;
414 }
415
416 /*
417  * Returns -1 on fail, 0 on success
418  */
419 static inline int
420 reserve_avail_buf_mergeable(struct virtio_net *dev, struct vhost_virtqueue *vq,
421                                 uint32_t size, struct buf_vector *buf_vec,
422                                 uint16_t *num_buffers, uint16_t avail_head)
423 {
424         uint16_t cur_idx;
425         uint32_t vec_idx = 0;
426         uint16_t tries = 0;
427
428         uint16_t head_idx = 0;
429         uint16_t len = 0;
430
431         *num_buffers = 0;
432         cur_idx  = vq->last_avail_idx;
433
434         while (size > 0) {
435                 if (unlikely(cur_idx == avail_head))
436                         return -1;
437
438                 if (unlikely(fill_vec_buf(dev, vq, cur_idx, &vec_idx, buf_vec,
439                                                 &head_idx, &len) < 0))
440                         return -1;
441                 len = RTE_MIN(len, size);
442                 update_shadow_used_ring(vq, head_idx, len);
443                 size -= len;
444
445                 cur_idx++;
446                 tries++;
447                 *num_buffers += 1;
448
449                 /*
450                  * if we tried all available ring items, and still
451                  * can't get enough buf, it means something abnormal
452                  * happened.
453                  */
454                 if (unlikely(tries >= vq->size))
455                         return -1;
456         }
457
458         return 0;
459 }
460
461 static inline int __attribute__((always_inline))
462 copy_mbuf_to_desc_mergeable(struct virtio_net *dev, struct rte_mbuf *m,
463                             struct buf_vector *buf_vec, uint16_t num_buffers)
464 {
465         struct virtio_net_hdr_mrg_rxbuf virtio_hdr = {{0, 0, 0, 0, 0, 0}, 0};
466         uint32_t vec_idx = 0;
467         uint64_t desc_addr;
468         uint32_t mbuf_offset, mbuf_avail;
469         uint32_t desc_offset, desc_avail;
470         uint32_t cpy_len;
471         uint64_t hdr_addr, hdr_phys_addr;
472         struct rte_mbuf *hdr_mbuf;
473
474         if (unlikely(m == NULL))
475                 return -1;
476
477         desc_addr = rte_vhost_gpa_to_vva(dev->mem, buf_vec[vec_idx].buf_addr);
478         if (buf_vec[vec_idx].buf_len < dev->vhost_hlen || !desc_addr)
479                 return -1;
480
481         hdr_mbuf = m;
482         hdr_addr = desc_addr;
483         hdr_phys_addr = buf_vec[vec_idx].buf_addr;
484         rte_prefetch0((void *)(uintptr_t)hdr_addr);
485
486         virtio_hdr.num_buffers = num_buffers;
487         LOG_DEBUG(VHOST_DATA, "(%d) RX: num merge buffers %d\n",
488                 dev->vid, num_buffers);
489
490         desc_avail  = buf_vec[vec_idx].buf_len - dev->vhost_hlen;
491         desc_offset = dev->vhost_hlen;
492
493         mbuf_avail  = rte_pktmbuf_data_len(m);
494         mbuf_offset = 0;
495         while (mbuf_avail != 0 || m->next != NULL) {
496                 /* done with current desc buf, get the next one */
497                 if (desc_avail == 0) {
498                         vec_idx++;
499                         desc_addr = rte_vhost_gpa_to_vva(dev->mem,
500                                         buf_vec[vec_idx].buf_addr);
501                         if (unlikely(!desc_addr))
502                                 return -1;
503
504                         /* Prefetch buffer address. */
505                         rte_prefetch0((void *)(uintptr_t)desc_addr);
506                         desc_offset = 0;
507                         desc_avail  = buf_vec[vec_idx].buf_len;
508                 }
509
510                 /* done with current mbuf, get the next one */
511                 if (mbuf_avail == 0) {
512                         m = m->next;
513
514                         mbuf_offset = 0;
515                         mbuf_avail  = rte_pktmbuf_data_len(m);
516                 }
517
518                 if (hdr_addr) {
519                         virtio_enqueue_offload(hdr_mbuf, &virtio_hdr.hdr);
520                         copy_virtio_net_hdr(dev, hdr_addr, virtio_hdr);
521                         vhost_log_write(dev, hdr_phys_addr, dev->vhost_hlen);
522                         PRINT_PACKET(dev, (uintptr_t)hdr_addr,
523                                      dev->vhost_hlen, 0);
524
525                         hdr_addr = 0;
526                 }
527
528                 cpy_len = RTE_MIN(desc_avail, mbuf_avail);
529                 rte_memcpy((void *)((uintptr_t)(desc_addr + desc_offset)),
530                         rte_pktmbuf_mtod_offset(m, void *, mbuf_offset),
531                         cpy_len);
532                 vhost_log_write(dev, buf_vec[vec_idx].buf_addr + desc_offset,
533                         cpy_len);
534                 PRINT_PACKET(dev, (uintptr_t)(desc_addr + desc_offset),
535                         cpy_len, 0);
536
537                 mbuf_avail  -= cpy_len;
538                 mbuf_offset += cpy_len;
539                 desc_avail  -= cpy_len;
540                 desc_offset += cpy_len;
541         }
542
543         return 0;
544 }
545
546 static inline uint32_t __attribute__((always_inline))
547 virtio_dev_merge_rx(struct virtio_net *dev, uint16_t queue_id,
548         struct rte_mbuf **pkts, uint32_t count)
549 {
550         struct vhost_virtqueue *vq;
551         uint32_t pkt_idx = 0;
552         uint16_t num_buffers;
553         struct buf_vector buf_vec[BUF_VECTOR_MAX];
554         uint16_t avail_head;
555
556         LOG_DEBUG(VHOST_DATA, "(%d) %s\n", dev->vid, __func__);
557         if (unlikely(!is_valid_virt_queue_idx(queue_id, 0, dev->virt_qp_nb))) {
558                 RTE_LOG(ERR, VHOST_DATA, "(%d) %s: invalid virtqueue idx %d.\n",
559                         dev->vid, __func__, queue_id);
560                 return 0;
561         }
562
563         vq = dev->virtqueue[queue_id];
564         if (unlikely(vq->enabled == 0))
565                 return 0;
566
567         count = RTE_MIN((uint32_t)MAX_PKT_BURST, count);
568         if (count == 0)
569                 return 0;
570
571         rte_prefetch0(&vq->avail->ring[vq->last_avail_idx & (vq->size - 1)]);
572
573         vq->shadow_used_idx = 0;
574         avail_head = *((volatile uint16_t *)&vq->avail->idx);
575         for (pkt_idx = 0; pkt_idx < count; pkt_idx++) {
576                 uint32_t pkt_len = pkts[pkt_idx]->pkt_len + dev->vhost_hlen;
577
578                 if (unlikely(reserve_avail_buf_mergeable(dev, vq,
579                                                 pkt_len, buf_vec, &num_buffers,
580                                                 avail_head) < 0)) {
581                         LOG_DEBUG(VHOST_DATA,
582                                 "(%d) failed to get enough desc from vring\n",
583                                 dev->vid);
584                         vq->shadow_used_idx -= num_buffers;
585                         break;
586                 }
587
588                 LOG_DEBUG(VHOST_DATA, "(%d) current index %d | end index %d\n",
589                         dev->vid, vq->last_avail_idx,
590                         vq->last_avail_idx + num_buffers);
591
592                 if (copy_mbuf_to_desc_mergeable(dev, pkts[pkt_idx],
593                                                 buf_vec, num_buffers) < 0) {
594                         vq->shadow_used_idx -= num_buffers;
595                         break;
596                 }
597
598                 vq->last_avail_idx += num_buffers;
599         }
600
601         if (likely(vq->shadow_used_idx)) {
602                 flush_shadow_used_ring(dev, vq);
603
604                 /* flush used->idx update before we read avail->flags. */
605                 rte_mb();
606
607                 /* Kick the guest if necessary. */
608                 if (!(vq->avail->flags & VRING_AVAIL_F_NO_INTERRUPT)
609                                 && (vq->callfd >= 0))
610                         eventfd_write(vq->callfd, (eventfd_t)1);
611         }
612
613         return pkt_idx;
614 }
615
616 uint16_t
617 rte_vhost_enqueue_burst(int vid, uint16_t queue_id,
618         struct rte_mbuf **pkts, uint16_t count)
619 {
620         struct virtio_net *dev = get_device(vid);
621
622         if (!dev)
623                 return 0;
624
625         if (dev->features & (1 << VIRTIO_NET_F_MRG_RXBUF))
626                 return virtio_dev_merge_rx(dev, queue_id, pkts, count);
627         else
628                 return virtio_dev_rx(dev, queue_id, pkts, count);
629 }
630
631 static inline bool
632 virtio_net_with_host_offload(struct virtio_net *dev)
633 {
634         if (dev->features &
635                         (VIRTIO_NET_F_CSUM | VIRTIO_NET_F_HOST_ECN |
636                          VIRTIO_NET_F_HOST_TSO4 | VIRTIO_NET_F_HOST_TSO6 |
637                          VIRTIO_NET_F_HOST_UFO))
638                 return true;
639
640         return false;
641 }
642
643 static void
644 parse_ethernet(struct rte_mbuf *m, uint16_t *l4_proto, void **l4_hdr)
645 {
646         struct ipv4_hdr *ipv4_hdr;
647         struct ipv6_hdr *ipv6_hdr;
648         void *l3_hdr = NULL;
649         struct ether_hdr *eth_hdr;
650         uint16_t ethertype;
651
652         eth_hdr = rte_pktmbuf_mtod(m, struct ether_hdr *);
653
654         m->l2_len = sizeof(struct ether_hdr);
655         ethertype = rte_be_to_cpu_16(eth_hdr->ether_type);
656
657         if (ethertype == ETHER_TYPE_VLAN) {
658                 struct vlan_hdr *vlan_hdr = (struct vlan_hdr *)(eth_hdr + 1);
659
660                 m->l2_len += sizeof(struct vlan_hdr);
661                 ethertype = rte_be_to_cpu_16(vlan_hdr->eth_proto);
662         }
663
664         l3_hdr = (char *)eth_hdr + m->l2_len;
665
666         switch (ethertype) {
667         case ETHER_TYPE_IPv4:
668                 ipv4_hdr = (struct ipv4_hdr *)l3_hdr;
669                 *l4_proto = ipv4_hdr->next_proto_id;
670                 m->l3_len = (ipv4_hdr->version_ihl & 0x0f) * 4;
671                 *l4_hdr = (char *)l3_hdr + m->l3_len;
672                 m->ol_flags |= PKT_TX_IPV4;
673                 break;
674         case ETHER_TYPE_IPv6:
675                 ipv6_hdr = (struct ipv6_hdr *)l3_hdr;
676                 *l4_proto = ipv6_hdr->proto;
677                 m->l3_len = sizeof(struct ipv6_hdr);
678                 *l4_hdr = (char *)l3_hdr + m->l3_len;
679                 m->ol_flags |= PKT_TX_IPV6;
680                 break;
681         default:
682                 m->l3_len = 0;
683                 *l4_proto = 0;
684                 *l4_hdr = NULL;
685                 break;
686         }
687 }
688
689 static inline void __attribute__((always_inline))
690 vhost_dequeue_offload(struct virtio_net_hdr *hdr, struct rte_mbuf *m)
691 {
692         uint16_t l4_proto = 0;
693         void *l4_hdr = NULL;
694         struct tcp_hdr *tcp_hdr = NULL;
695
696         if (hdr->flags == 0 && hdr->gso_type == VIRTIO_NET_HDR_GSO_NONE)
697                 return;
698
699         parse_ethernet(m, &l4_proto, &l4_hdr);
700         if (hdr->flags == VIRTIO_NET_HDR_F_NEEDS_CSUM) {
701                 if (hdr->csum_start == (m->l2_len + m->l3_len)) {
702                         switch (hdr->csum_offset) {
703                         case (offsetof(struct tcp_hdr, cksum)):
704                                 if (l4_proto == IPPROTO_TCP)
705                                         m->ol_flags |= PKT_TX_TCP_CKSUM;
706                                 break;
707                         case (offsetof(struct udp_hdr, dgram_cksum)):
708                                 if (l4_proto == IPPROTO_UDP)
709                                         m->ol_flags |= PKT_TX_UDP_CKSUM;
710                                 break;
711                         case (offsetof(struct sctp_hdr, cksum)):
712                                 if (l4_proto == IPPROTO_SCTP)
713                                         m->ol_flags |= PKT_TX_SCTP_CKSUM;
714                                 break;
715                         default:
716                                 break;
717                         }
718                 }
719         }
720
721         if (l4_hdr && hdr->gso_type != VIRTIO_NET_HDR_GSO_NONE) {
722                 switch (hdr->gso_type & ~VIRTIO_NET_HDR_GSO_ECN) {
723                 case VIRTIO_NET_HDR_GSO_TCPV4:
724                 case VIRTIO_NET_HDR_GSO_TCPV6:
725                         tcp_hdr = (struct tcp_hdr *)l4_hdr;
726                         m->ol_flags |= PKT_TX_TCP_SEG;
727                         m->tso_segsz = hdr->gso_size;
728                         m->l4_len = (tcp_hdr->data_off & 0xf0) >> 2;
729                         break;
730                 default:
731                         RTE_LOG(WARNING, VHOST_DATA,
732                                 "unsupported gso type %u.\n", hdr->gso_type);
733                         break;
734                 }
735         }
736 }
737
738 #define RARP_PKT_SIZE   64
739
740 static int
741 make_rarp_packet(struct rte_mbuf *rarp_mbuf, const struct ether_addr *mac)
742 {
743         struct ether_hdr *eth_hdr;
744         struct arp_hdr  *rarp;
745
746         if (rarp_mbuf->buf_len < 64) {
747                 RTE_LOG(WARNING, VHOST_DATA,
748                         "failed to make RARP; mbuf size too small %u (< %d)\n",
749                         rarp_mbuf->buf_len, RARP_PKT_SIZE);
750                 return -1;
751         }
752
753         /* Ethernet header. */
754         eth_hdr = rte_pktmbuf_mtod_offset(rarp_mbuf, struct ether_hdr *, 0);
755         memset(eth_hdr->d_addr.addr_bytes, 0xff, ETHER_ADDR_LEN);
756         ether_addr_copy(mac, &eth_hdr->s_addr);
757         eth_hdr->ether_type = htons(ETHER_TYPE_RARP);
758
759         /* RARP header. */
760         rarp = (struct arp_hdr *)(eth_hdr + 1);
761         rarp->arp_hrd = htons(ARP_HRD_ETHER);
762         rarp->arp_pro = htons(ETHER_TYPE_IPv4);
763         rarp->arp_hln = ETHER_ADDR_LEN;
764         rarp->arp_pln = 4;
765         rarp->arp_op  = htons(ARP_OP_REVREQUEST);
766
767         ether_addr_copy(mac, &rarp->arp_data.arp_sha);
768         ether_addr_copy(mac, &rarp->arp_data.arp_tha);
769         memset(&rarp->arp_data.arp_sip, 0x00, 4);
770         memset(&rarp->arp_data.arp_tip, 0x00, 4);
771
772         rarp_mbuf->pkt_len  = rarp_mbuf->data_len = RARP_PKT_SIZE;
773
774         return 0;
775 }
776
777 static inline void __attribute__((always_inline))
778 put_zmbuf(struct zcopy_mbuf *zmbuf)
779 {
780         zmbuf->in_use = 0;
781 }
782
783 static inline int __attribute__((always_inline))
784 copy_desc_to_mbuf(struct virtio_net *dev, struct vring_desc *descs,
785                   uint16_t max_desc, struct rte_mbuf *m, uint16_t desc_idx,
786                   struct rte_mempool *mbuf_pool)
787 {
788         struct vring_desc *desc;
789         uint64_t desc_addr;
790         uint32_t desc_avail, desc_offset;
791         uint32_t mbuf_avail, mbuf_offset;
792         uint32_t cpy_len;
793         struct rte_mbuf *cur = m, *prev = m;
794         struct virtio_net_hdr *hdr = NULL;
795         /* A counter to avoid desc dead loop chain */
796         uint32_t nr_desc = 1;
797
798         desc = &descs[desc_idx];
799         if (unlikely((desc->len < dev->vhost_hlen)) ||
800                         (desc->flags & VRING_DESC_F_INDIRECT))
801                 return -1;
802
803         desc_addr = rte_vhost_gpa_to_vva(dev->mem, desc->addr);
804         if (unlikely(!desc_addr))
805                 return -1;
806
807         if (virtio_net_with_host_offload(dev)) {
808                 hdr = (struct virtio_net_hdr *)((uintptr_t)desc_addr);
809                 rte_prefetch0(hdr);
810         }
811
812         /*
813          * A virtio driver normally uses at least 2 desc buffers
814          * for Tx: the first for storing the header, and others
815          * for storing the data.
816          */
817         if (likely((desc->len == dev->vhost_hlen) &&
818                    (desc->flags & VRING_DESC_F_NEXT) != 0)) {
819                 desc = &descs[desc->next];
820                 if (unlikely(desc->flags & VRING_DESC_F_INDIRECT))
821                         return -1;
822
823                 desc_addr = rte_vhost_gpa_to_vva(dev->mem, desc->addr);
824                 if (unlikely(!desc_addr))
825                         return -1;
826
827                 desc_offset = 0;
828                 desc_avail  = desc->len;
829                 nr_desc    += 1;
830         } else {
831                 desc_avail  = desc->len - dev->vhost_hlen;
832                 desc_offset = dev->vhost_hlen;
833         }
834
835         rte_prefetch0((void *)(uintptr_t)(desc_addr + desc_offset));
836
837         PRINT_PACKET(dev, (uintptr_t)(desc_addr + desc_offset), desc_avail, 0);
838
839         mbuf_offset = 0;
840         mbuf_avail  = m->buf_len - RTE_PKTMBUF_HEADROOM;
841         while (1) {
842                 uint64_t hpa;
843
844                 cpy_len = RTE_MIN(desc_avail, mbuf_avail);
845
846                 /*
847                  * A desc buf might across two host physical pages that are
848                  * not continuous. In such case (gpa_to_hpa returns 0), data
849                  * will be copied even though zero copy is enabled.
850                  */
851                 if (unlikely(dev->dequeue_zero_copy && (hpa = gpa_to_hpa(dev,
852                                         desc->addr + desc_offset, cpy_len)))) {
853                         cur->data_len = cpy_len;
854                         cur->data_off = 0;
855                         cur->buf_addr = (void *)(uintptr_t)desc_addr;
856                         cur->buf_physaddr = hpa;
857
858                         /*
859                          * In zero copy mode, one mbuf can only reference data
860                          * for one or partial of one desc buff.
861                          */
862                         mbuf_avail = cpy_len;
863                 } else {
864                         rte_memcpy(rte_pktmbuf_mtod_offset(cur, void *,
865                                                            mbuf_offset),
866                                 (void *)((uintptr_t)(desc_addr + desc_offset)),
867                                 cpy_len);
868                 }
869
870                 mbuf_avail  -= cpy_len;
871                 mbuf_offset += cpy_len;
872                 desc_avail  -= cpy_len;
873                 desc_offset += cpy_len;
874
875                 /* This desc reaches to its end, get the next one */
876                 if (desc_avail == 0) {
877                         if ((desc->flags & VRING_DESC_F_NEXT) == 0)
878                                 break;
879
880                         if (unlikely(desc->next >= max_desc ||
881                                      ++nr_desc > max_desc))
882                                 return -1;
883                         desc = &descs[desc->next];
884                         if (unlikely(desc->flags & VRING_DESC_F_INDIRECT))
885                                 return -1;
886
887                         desc_addr = rte_vhost_gpa_to_vva(dev->mem, desc->addr);
888                         if (unlikely(!desc_addr))
889                                 return -1;
890
891                         rte_prefetch0((void *)(uintptr_t)desc_addr);
892
893                         desc_offset = 0;
894                         desc_avail  = desc->len;
895
896                         PRINT_PACKET(dev, (uintptr_t)desc_addr, desc->len, 0);
897                 }
898
899                 /*
900                  * This mbuf reaches to its end, get a new one
901                  * to hold more data.
902                  */
903                 if (mbuf_avail == 0) {
904                         cur = rte_pktmbuf_alloc(mbuf_pool);
905                         if (unlikely(cur == NULL)) {
906                                 RTE_LOG(ERR, VHOST_DATA, "Failed to "
907                                         "allocate memory for mbuf.\n");
908                                 return -1;
909                         }
910
911                         prev->next = cur;
912                         prev->data_len = mbuf_offset;
913                         m->nb_segs += 1;
914                         m->pkt_len += mbuf_offset;
915                         prev = cur;
916
917                         mbuf_offset = 0;
918                         mbuf_avail  = cur->buf_len - RTE_PKTMBUF_HEADROOM;
919                 }
920         }
921
922         prev->data_len = mbuf_offset;
923         m->pkt_len    += mbuf_offset;
924
925         if (hdr)
926                 vhost_dequeue_offload(hdr, m);
927
928         return 0;
929 }
930
931 static inline void __attribute__((always_inline))
932 update_used_ring(struct virtio_net *dev, struct vhost_virtqueue *vq,
933                  uint32_t used_idx, uint32_t desc_idx)
934 {
935         vq->used->ring[used_idx].id  = desc_idx;
936         vq->used->ring[used_idx].len = 0;
937         vhost_log_used_vring(dev, vq,
938                         offsetof(struct vring_used, ring[used_idx]),
939                         sizeof(vq->used->ring[used_idx]));
940 }
941
942 static inline void __attribute__((always_inline))
943 update_used_idx(struct virtio_net *dev, struct vhost_virtqueue *vq,
944                 uint32_t count)
945 {
946         if (unlikely(count == 0))
947                 return;
948
949         rte_smp_wmb();
950         rte_smp_rmb();
951
952         vq->used->idx += count;
953         vhost_log_used_vring(dev, vq, offsetof(struct vring_used, idx),
954                         sizeof(vq->used->idx));
955
956         /* Kick guest if required. */
957         if (!(vq->avail->flags & VRING_AVAIL_F_NO_INTERRUPT)
958                         && (vq->callfd >= 0))
959                 eventfd_write(vq->callfd, (eventfd_t)1);
960 }
961
962 static inline struct zcopy_mbuf *__attribute__((always_inline))
963 get_zmbuf(struct vhost_virtqueue *vq)
964 {
965         uint16_t i;
966         uint16_t last;
967         int tries = 0;
968
969         /* search [last_zmbuf_idx, zmbuf_size) */
970         i = vq->last_zmbuf_idx;
971         last = vq->zmbuf_size;
972
973 again:
974         for (; i < last; i++) {
975                 if (vq->zmbufs[i].in_use == 0) {
976                         vq->last_zmbuf_idx = i + 1;
977                         vq->zmbufs[i].in_use = 1;
978                         return &vq->zmbufs[i];
979                 }
980         }
981
982         tries++;
983         if (tries == 1) {
984                 /* search [0, last_zmbuf_idx) */
985                 i = 0;
986                 last = vq->last_zmbuf_idx;
987                 goto again;
988         }
989
990         return NULL;
991 }
992
993 static inline bool __attribute__((always_inline))
994 mbuf_is_consumed(struct rte_mbuf *m)
995 {
996         while (m) {
997                 if (rte_mbuf_refcnt_read(m) > 1)
998                         return false;
999                 m = m->next;
1000         }
1001
1002         return true;
1003 }
1004
1005 uint16_t
1006 rte_vhost_dequeue_burst(int vid, uint16_t queue_id,
1007         struct rte_mempool *mbuf_pool, struct rte_mbuf **pkts, uint16_t count)
1008 {
1009         struct virtio_net *dev;
1010         struct rte_mbuf *rarp_mbuf = NULL;
1011         struct vhost_virtqueue *vq;
1012         uint32_t desc_indexes[MAX_PKT_BURST];
1013         uint32_t used_idx;
1014         uint32_t i = 0;
1015         uint16_t free_entries;
1016         uint16_t avail_idx;
1017
1018         dev = get_device(vid);
1019         if (!dev)
1020                 return 0;
1021
1022         if (unlikely(!is_valid_virt_queue_idx(queue_id, 1, dev->virt_qp_nb))) {
1023                 RTE_LOG(ERR, VHOST_DATA, "(%d) %s: invalid virtqueue idx %d.\n",
1024                         dev->vid, __func__, queue_id);
1025                 return 0;
1026         }
1027
1028         vq = dev->virtqueue[queue_id];
1029         if (unlikely(vq->enabled == 0))
1030                 return 0;
1031
1032         if (unlikely(dev->dequeue_zero_copy)) {
1033                 struct zcopy_mbuf *zmbuf, *next;
1034                 int nr_updated = 0;
1035
1036                 for (zmbuf = TAILQ_FIRST(&vq->zmbuf_list);
1037                      zmbuf != NULL; zmbuf = next) {
1038                         next = TAILQ_NEXT(zmbuf, next);
1039
1040                         if (mbuf_is_consumed(zmbuf->mbuf)) {
1041                                 used_idx = vq->last_used_idx++ & (vq->size - 1);
1042                                 update_used_ring(dev, vq, used_idx,
1043                                                  zmbuf->desc_idx);
1044                                 nr_updated += 1;
1045
1046                                 TAILQ_REMOVE(&vq->zmbuf_list, zmbuf, next);
1047                                 rte_pktmbuf_free(zmbuf->mbuf);
1048                                 put_zmbuf(zmbuf);
1049                                 vq->nr_zmbuf -= 1;
1050                         }
1051                 }
1052
1053                 update_used_idx(dev, vq, nr_updated);
1054         }
1055
1056         /*
1057          * Construct a RARP broadcast packet, and inject it to the "pkts"
1058          * array, to looks like that guest actually send such packet.
1059          *
1060          * Check user_send_rarp() for more information.
1061          *
1062          * broadcast_rarp shares a cacheline in the virtio_net structure
1063          * with some fields that are accessed during enqueue and
1064          * rte_atomic16_cmpset() causes a write if using cmpxchg. This could
1065          * result in false sharing between enqueue and dequeue.
1066          *
1067          * Prevent unnecessary false sharing by reading broadcast_rarp first
1068          * and only performing cmpset if the read indicates it is likely to
1069          * be set.
1070          */
1071
1072         if (unlikely(rte_atomic16_read(&dev->broadcast_rarp) &&
1073                         rte_atomic16_cmpset((volatile uint16_t *)
1074                                 &dev->broadcast_rarp.cnt, 1, 0))) {
1075
1076                 rarp_mbuf = rte_pktmbuf_alloc(mbuf_pool);
1077                 if (rarp_mbuf == NULL) {
1078                         RTE_LOG(ERR, VHOST_DATA,
1079                                 "Failed to allocate memory for mbuf.\n");
1080                         return 0;
1081                 }
1082
1083                 if (make_rarp_packet(rarp_mbuf, &dev->mac)) {
1084                         rte_pktmbuf_free(rarp_mbuf);
1085                         rarp_mbuf = NULL;
1086                 } else {
1087                         count -= 1;
1088                 }
1089         }
1090
1091         free_entries = *((volatile uint16_t *)&vq->avail->idx) -
1092                         vq->last_avail_idx;
1093         if (free_entries == 0)
1094                 goto out;
1095
1096         LOG_DEBUG(VHOST_DATA, "(%d) %s\n", dev->vid, __func__);
1097
1098         /* Prefetch available and used ring */
1099         avail_idx = vq->last_avail_idx & (vq->size - 1);
1100         used_idx  = vq->last_used_idx  & (vq->size - 1);
1101         rte_prefetch0(&vq->avail->ring[avail_idx]);
1102         rte_prefetch0(&vq->used->ring[used_idx]);
1103
1104         count = RTE_MIN(count, MAX_PKT_BURST);
1105         count = RTE_MIN(count, free_entries);
1106         LOG_DEBUG(VHOST_DATA, "(%d) about to dequeue %u buffers\n",
1107                         dev->vid, count);
1108
1109         /* Retrieve all of the head indexes first to avoid caching issues. */
1110         for (i = 0; i < count; i++) {
1111                 avail_idx = (vq->last_avail_idx + i) & (vq->size - 1);
1112                 used_idx  = (vq->last_used_idx  + i) & (vq->size - 1);
1113                 desc_indexes[i] = vq->avail->ring[avail_idx];
1114
1115                 if (likely(dev->dequeue_zero_copy == 0))
1116                         update_used_ring(dev, vq, used_idx, desc_indexes[i]);
1117         }
1118
1119         /* Prefetch descriptor index. */
1120         rte_prefetch0(&vq->desc[desc_indexes[0]]);
1121         for (i = 0; i < count; i++) {
1122                 struct vring_desc *desc;
1123                 uint16_t sz, idx;
1124                 int err;
1125
1126                 if (likely(i + 1 < count))
1127                         rte_prefetch0(&vq->desc[desc_indexes[i + 1]]);
1128
1129                 if (vq->desc[desc_indexes[i]].flags & VRING_DESC_F_INDIRECT) {
1130                         desc = (struct vring_desc *)(uintptr_t)
1131                                 rte_vhost_gpa_to_vva(dev->mem,
1132                                         vq->desc[desc_indexes[i]].addr);
1133                         if (unlikely(!desc))
1134                                 break;
1135
1136                         rte_prefetch0(desc);
1137                         sz = vq->desc[desc_indexes[i]].len / sizeof(*desc);
1138                         idx = 0;
1139                 } else {
1140                         desc = vq->desc;
1141                         sz = vq->size;
1142                         idx = desc_indexes[i];
1143                 }
1144
1145                 pkts[i] = rte_pktmbuf_alloc(mbuf_pool);
1146                 if (unlikely(pkts[i] == NULL)) {
1147                         RTE_LOG(ERR, VHOST_DATA,
1148                                 "Failed to allocate memory for mbuf.\n");
1149                         break;
1150                 }
1151
1152                 err = copy_desc_to_mbuf(dev, desc, sz, pkts[i], idx, mbuf_pool);
1153                 if (unlikely(err)) {
1154                         rte_pktmbuf_free(pkts[i]);
1155                         break;
1156                 }
1157
1158                 if (unlikely(dev->dequeue_zero_copy)) {
1159                         struct zcopy_mbuf *zmbuf;
1160
1161                         zmbuf = get_zmbuf(vq);
1162                         if (!zmbuf) {
1163                                 rte_pktmbuf_free(pkts[i]);
1164                                 break;
1165                         }
1166                         zmbuf->mbuf = pkts[i];
1167                         zmbuf->desc_idx = desc_indexes[i];
1168
1169                         /*
1170                          * Pin lock the mbuf; we will check later to see
1171                          * whether the mbuf is freed (when we are the last
1172                          * user) or not. If that's the case, we then could
1173                          * update the used ring safely.
1174                          */
1175                         rte_mbuf_refcnt_update(pkts[i], 1);
1176
1177                         vq->nr_zmbuf += 1;
1178                         TAILQ_INSERT_TAIL(&vq->zmbuf_list, zmbuf, next);
1179                 }
1180         }
1181         vq->last_avail_idx += i;
1182
1183         if (likely(dev->dequeue_zero_copy == 0)) {
1184                 vq->last_used_idx += i;
1185                 update_used_idx(dev, vq, i);
1186         }
1187
1188 out:
1189         if (unlikely(rarp_mbuf != NULL)) {
1190                 /*
1191                  * Inject it to the head of "pkts" array, so that switch's mac
1192                  * learning table will get updated first.
1193                  */
1194                 memmove(&pkts[1], pkts, i * sizeof(struct rte_mbuf *));
1195                 pkts[0] = rarp_mbuf;
1196                 i += 1;
1197         }
1198
1199         return i;
1200 }