Patchwork [v2] add event queueing to USB HID

login
register
mail settings
Submitter Paolo Bonzini
Date Jan. 12, 2011, 12:19 p.m.
Message ID <1294834760-24996-1-git-send-email-pbonzini@redhat.com>
Download mbox | patch
Permalink /patch/78560/
State New
Headers show

Comments

Paolo Bonzini - Jan. 12, 2011, 12:19 p.m.
The polling nature of the USB HID device makes it very hard to double
click or drag while on a high-latency VNC connection.  This patch,
based on work done in the Xen qemu-dm tree by Ian Jackson, fixes this
bug by adding an event queue to the device.  The event queue associates
each movement with the correct button state, and remembers all button
presses and releases as well.

Cc: Gerd Hoffman <kraxel@redhat.com>
Signed-off-by: Ian Jackson <ian.jackson@eu.citrix.com>
Signed-off-by: Stefano Stabellini <stefano.stabellini@eu.citrix.com>
Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
---
        For v2 I changed the head/tail implementation of the FIFO buffer
        (which was buggy when the queue became full) to head/count.
        I then removed "have_data", which is the same as count>0
        for pointer devices and the same as "changed" for keyboards.
        This made event merging more correct than in Ian's code and
        easier to understand than my v1.

        I left the "changed" member in USBHIDState, rather than moving it
        to the keyboard, because it is useful to handle the idle period
        (in USB_TOKEN_IN) in a device-independent way.  Without it the
        code became more messy.

 hw/usb-hid.c |  221 +++++++++++++++++++++++++++++++++-------------------------
 1 files changed, 127 insertions(+), 94 deletions(-)
Paolo Bonzini - Jan. 12, 2011, 1:01 p.m.
On 01/12/2011 01:34 PM, Ian Jackson wrote:
> Paolo Bonzini writes ("[PATCH v2] add event queueing to USB HID"):
>>          For v2 I changed the head/tail implementation of the FIFO buffer
>>          (which was buggy when the queue became full) to head/count.
>>          I then removed "have_data", which is the same as count>0
>>          for pointer devices and the same as "changed" for keyboards.
>>          This made event merging more correct than in Ian's code and
>>          easier to understand than my v1.
>
> Thanks.  Was my code buggy then ?  It's possible; the event merging
> case is not easy to trigger in testing.

It's all pretty academic as in practice it worked well.  The queue-full 
code would never trigger in usb_pointer_event, and instead the queue 
would be instantly emptied when a 17th event arrived.  This is lucky 
actually, because the device would also stop unqueuing from a full queue 
if it had SET_IDLE 0.  Both bugs happened because head==tail could mean 
both "empty queue" and "full queue".  I'm not even sure it's possible to 
fill the queue in practice; even with a very high latency you'd have to 
do 8 clicks in say half a second.  I didn't try with a shorter queue, 
which of course would have made the problems evident.

>>          I left the "changed" member in USBHIDState, rather than moving it
>>          to the keyboard, because it is useful to handle the idle period
>>          (in USB_TOKEN_IN) in a device-independent way.  Without it the
>>          code became more messy.
>
> This leaves the same information recorded in the driver in two places
> and is therefore IMO a bad idea.  I still think the way I did this is
> best: have a common helper function used by the keyboard and pointer
> code to deal with the idle handling.

I don't disagree, but I think this is better left for a separate patch. 
  I see three reasons for this:

1) I would like to understand better the relation between GET_REPORT and 
TOKEN_IN.  If an event occurs between two TOKEN_IN messages, and the OS 
sends a GET_REPORT in between, should the second TOKEN_IN return 
USB_RET_NAK or not?  With your patch it will, with current QEMU and my 
patch it won't.  In this sense, the "changed" flag is recording slightly 
different information at least in my version of the code.

2) if buffering is implemented for the keyboard device (and it probably 
should) most of the differences would go away again.

3) Secondarily, this is the only part of your patch that would need 
adjustments, since finite idle delays are now implemented.

Paolo
Ian Jackson - Jan. 12, 2011, 1:05 p.m.
Paolo Bonzini writes ("Re: [PATCH v2] add event queueing to USB HID"):
> It's all pretty academic as in practice it worked well.  The queue-full 
> code would never trigger in usb_pointer_event, and instead the queue 
> would be instantly emptied when a 17th event arrived.  This is lucky 
> actually, because the device would also stop unqueuing from a full queue 
> if it had SET_IDLE 0.  Both bugs happened because head==tail could mean 
> both "empty queue" and "full queue".  I'm not even sure it's possible to 
> fill the queue in practice; even with a very high latency you'd have to 
> do 8 clicks in say half a second.  I didn't try with a shorter queue, 
> which of course would have made the problems evident.

Ah.  head==tail was supposed to mean empty (as is conventional); I
guess my "full" test just had an off-by-one error.

> I don't disagree, but I think this is better left for a separate patch. 
>   I see three reasons for this:
> 
> 1) I would like to understand better the relation between GET_REPORT and 
> TOKEN_IN.  If an event occurs between two TOKEN_IN messages, and the OS 
> sends a GET_REPORT in between, should the second TOKEN_IN return 
> USB_RET_NAK or not?  With your patch it will, with current QEMU and my 
> patch it won't.  In this sense, the "changed" flag is recording slightly 
> different information at least in my version of the code.

Hrm.

> 2) if buffering is implemented for the keyboard device (and it probably 
> should) most of the differences would go away again.

True.

> 3) Secondarily, this is the only part of your patch that would need 
> adjustments, since finite idle delays are now implemented.

Right.

OK.  Thanks for your work.


Acked-by: Ian Jackson <ian.jackson@eu.citrix.com>

Ian.
Gerd Hoffmann - Jan. 12, 2011, 4:27 p.m.
Hi,

>>> I left the "changed" member in USBHIDState, rather than moving it
>>> to the keyboard, because it is useful to handle the idle period
>>> (in USB_TOKEN_IN) in a device-independent way. Without it the
>>> code became more messy.
>>
>> This leaves the same information recorded in the driver in two places
>> and is therefore IMO a bad idea. I still think the way I did this is
>> best: have a common helper function used by the keyboard and pointer
>> code to deal with the idle handling.
>
> I don't disagree, but I think this is better left for a separate patch.

Just use a queue for both pointer and keyboard -- problem solved ;)

Need a test case?  Connect with vncviewer, press F8, pick "Send 
Ctrl-Alt-Del" from the menu.  Works with ps/2 keyboard.  Doesn't work 
with usb keyboard.

cheers,
   Gerd

Patch

diff --git a/hw/usb-hid.c b/hw/usb-hid.c
index 882d933..5019cad 100644
--- a/hw/usb-hid.c
+++ b/hw/usb-hid.c
@@ -44,9 +44,19 @@ 
 #define USB_TABLET    2
 #define USB_KEYBOARD  3
 
+typedef struct USBPointerEvent {
+    int xdx, ydy; /* relative iff it's a mouse, otherwise absolute */
+    int dz, buttons_state;
+} USBPointerEvent;
+
+#define QUEUE_LENGTH    16 /* should be enough for a triple-click */
+#define QUEUE_MASK      (QUEUE_LENGTH-1u)
+#define QUEUE_INCR(v)   ((v)++, (v) &= QUEUE_MASK)
+
 typedef struct USBMouseState {
-    int dx, dy, dz, buttons_state;
-    int x, y;
+    USBPointerEvent queue[QUEUE_LENGTH];
+    unsigned head; /* index into circular queue */
+    unsigned n;
     int mouse_grabbed;
     QEMUPutMouseEntry *eh_entry;
 } USBMouseState;
@@ -414,31 +424,50 @@  static void usb_hid_changed(USBHIDState *hs)
         hs->datain(hs->datain_opaque);
 }
 
-static void usb_mouse_event(void *opaque,
-                            int dx1, int dy1, int dz1, int buttons_state)
-{
-    USBHIDState *hs = opaque;
-    USBMouseState *s = &hs->ptr;
-
-    s->dx += dx1;
-    s->dy += dy1;
-    s->dz += dz1;
-    s->buttons_state = buttons_state;
+static void usb_pointer_event_clear(USBPointerEvent *e, int buttons) {
+    e->xdx = e->ydy = e->dz = 0;
+    e->buttons_state = buttons;
+}
 
-    usb_hid_changed(hs);
+static void usb_pointer_event_combine(USBPointerEvent *e, int xyrel,
+                                      int x1, int y1, int z1) {
+    if (xyrel) {
+        e->xdx += x1;
+        e->ydy += y1;
+    } else {
+        e->xdx = x1;
+        e->ydy = y1;
+    }
+    e->dz += z1;
 }
 
-static void usb_tablet_event(void *opaque,
-			     int x, int y, int dz, int buttons_state)
+static void usb_pointer_event(void *opaque,
+                              int x1, int y1, int z1, int buttons_state)
 {
     USBHIDState *hs = opaque;
     USBMouseState *s = &hs->ptr;
+    unsigned use_slot = (s->head + s->n - 1) & QUEUE_MASK;
+    unsigned previous_slot = (use_slot - 1) & QUEUE_MASK;
 
-    s->x = x;
-    s->y = y;
-    s->dz += dz;
-    s->buttons_state = buttons_state;
-
+    /* We combine events where feasible to keep the queue small.  We shouldn't
+     * combine anything with the first event of a particular button state, as
+     * that would change the location of the button state change.  When the
+     * queue is empty, a second event is needed because we don't know if
+     * the first event changed the button state.  */
+    if (s->n == QUEUE_LENGTH) {
+        /* Queue full.  Discard old button state, combine motion normally.  */
+        s->queue[use_slot].buttons_state = buttons_state;
+    } else if (s->n < 2 ||
+               s->queue[use_slot].buttons_state != buttons_state ||
+               s->queue[previous_slot].buttons_state != s->queue[use_slot].buttons_state) {
+        /* Cannot or should not combine, so add an empty item to the queue.  */
+        QUEUE_INCR(use_slot);
+        s->n++;
+        usb_pointer_event_clear(&s->queue[use_slot], buttons_state);
+    }
+    usb_pointer_event_combine(&s->queue[use_slot],
+                              hs->kind == USB_MOUSE,
+                              x1, y1, z1);
     usb_hid_changed(hs);
 }
 
@@ -506,83 +535,91 @@  static inline int int_clamp(int val, int vmin, int vmax)
         return val;
 }
 
-static int usb_mouse_poll(USBHIDState *hs, uint8_t *buf, int len)
+static int usb_pointer_poll(USBHIDState *hs, uint8_t *buf, int len)
 {
     int dx, dy, dz, b, l;
+    int index;
     USBMouseState *s = &hs->ptr;
+    USBPointerEvent *e;
 
     if (!s->mouse_grabbed) {
         qemu_activate_mouse_event_handler(s->eh_entry);
-	s->mouse_grabbed = 1;
+        s->mouse_grabbed = 1;
     }
 
-    dx = int_clamp(s->dx, -127, 127);
-    dy = int_clamp(s->dy, -127, 127);
-    dz = int_clamp(s->dz, -127, 127);
+    /* When the buffer is empty, return the last event.  Relative
+       movements will all be zero.  */
+    index = (s->n ? s->head : s->head - 1);
+    e = &s->queue[index & QUEUE_MASK];
 
-    s->dx -= dx;
-    s->dy -= dy;
-    s->dz -= dz;
-
-    /* Appears we have to invert the wheel direction */
-    dz = 0 - dz;
+    if (hs->kind == USB_MOUSE) {
+        dx = int_clamp(e->xdx, -127, 127);
+        dy = int_clamp(e->ydy, -127, 127);
+        e->xdx -= dx;
+        e->ydy -= dy;
+    } else {
+        dx = e->xdx;
+        dy = e->ydy;
+    }
+    dz = int_clamp(e->dz, -127, 127);
+    e->dz -= dz;
 
     b = 0;
-    if (s->buttons_state & MOUSE_EVENT_LBUTTON)
+    if (e->buttons_state & MOUSE_EVENT_LBUTTON)
         b |= 0x01;
-    if (s->buttons_state & MOUSE_EVENT_RBUTTON)
+    if (e->buttons_state & MOUSE_EVENT_RBUTTON)
         b |= 0x02;
-    if (s->buttons_state & MOUSE_EVENT_MBUTTON)
+    if (e->buttons_state & MOUSE_EVENT_MBUTTON)
         b |= 0x04;
 
+    if (s->n &&
+        !e->dz &&
+        (hs->kind == USB_TABLET || (!e->xdx && !e->ydy))) {
+        /* that deals with this event */
+        QUEUE_INCR(s->head);
+        s->n--;
+    }
+
+    /* Appears we have to invert the wheel direction */
+    dz = 0 - dz;
     l = 0;
-    if (len > l)
-        buf[l ++] = b;
-    if (len > l)
-        buf[l ++] = dx;
-    if (len > l)
-        buf[l ++] = dy;
-    if (len > l)
-        buf[l ++] = dz;
-    return l;
-}
+    switch (hs->kind) {
+    case USB_MOUSE:
+        if (len > l)
+            buf[l++] = b;
+        if (len > l)
+            buf[l++] = dx;
+        if (len > l)
+            buf[l++] = dy;
+        if (len > l)
+            buf[l++] = dz;
+        break;
 
-static int usb_tablet_poll(USBHIDState *hs, uint8_t *buf, int len)
-{
-    int dz, b, l;
-    USBMouseState *s = &hs->ptr;
+    case USB_TABLET:
+        if (len > l)
+            buf[l++] = b;
+        if (len > l)
+            buf[l++] = dx & 0xff;
+        if (len > l)
+            buf[l++] = dx >> 8;
+        if (len > l)
+            buf[l++] = dy & 0xff;
+        if (len > l)
+            buf[l++] = dy >> 8;
+        if (len > l)
+            buf[l++] = dz;
+        break;
 
-    if (!s->mouse_grabbed) {
-        qemu_activate_mouse_event_handler(s->eh_entry);
-	s->mouse_grabbed = 1;
+    default:
+        abort();
     }
 
-    dz = int_clamp(s->dz, -127, 127);
-    s->dz -= dz;
-
-    /* Appears we have to invert the wheel direction */
-    dz = 0 - dz;
-    b = 0;
-    if (s->buttons_state & MOUSE_EVENT_LBUTTON)
-        b |= 0x01;
-    if (s->buttons_state & MOUSE_EVENT_RBUTTON)
-        b |= 0x02;
-    if (s->buttons_state & MOUSE_EVENT_MBUTTON)
-        b |= 0x04;
-
-    buf[0] = b;
-    buf[1] = s->x & 0xff;
-    buf[2] = s->x >> 8;
-    buf[3] = s->y & 0xff;
-    buf[4] = s->y >> 8;
-    buf[5] = dz;
-    l = 6;
-
     return l;
 }
 
-static int usb_keyboard_poll(USBKeyboardState *s, uint8_t *buf, int len)
+static int usb_keyboard_poll(USBHIDState *hs, uint8_t *buf, int len)
 {
+    USBKeyboardState *s = &hs->kbd;
     if (len < 2)
         return 0;
 
@@ -621,12 +658,9 @@  static void usb_mouse_handle_reset(USBDevice *dev)
 {
     USBHIDState *s = (USBHIDState *)dev;
 
-    s->ptr.dx = 0;
-    s->ptr.dy = 0;
-    s->ptr.dz = 0;
-    s->ptr.x = 0;
-    s->ptr.y = 0;
-    s->ptr.buttons_state = 0;
+    memset (s->ptr.queue, 0, sizeof (s->ptr.queue));
+    s->ptr.head = 0;
+    s->ptr.n = 0;
     s->protocol = 1;
 }
 
@@ -777,12 +811,10 @@  static int usb_hid_handle_control(USBDevice *dev, int request, int value,
         }
         break;
     case GET_REPORT:
-	if (s->kind == USB_MOUSE)
-            ret = usb_mouse_poll(s, data, length);
-	else if (s->kind == USB_TABLET)
-            ret = usb_tablet_poll(s, data, length);
+        if (s->kind == USB_MOUSE || s->kind == USB_TABLET)
+            ret = usb_pointer_poll(s, data, length);
         else if (s->kind == USB_KEYBOARD)
-            ret = usb_keyboard_poll(&s->kbd, data, length);
+            ret = usb_keyboard_poll(s, data, length);
         break;
     case SET_REPORT:
         if (s->kind == USB_KEYBOARD)
@@ -831,13 +863,14 @@  static int usb_hid_handle_data(USBDevice *dev, USBPacket *p)
             if (!s->changed && (!s->idle || s->next_idle_clock - curtime > 0))
                 return USB_RET_NAK;
             usb_hid_set_next_idle(s, curtime);
-            s->changed = 0;
-            if (s->kind == USB_MOUSE)
-                ret = usb_mouse_poll(s, p->data, p->len);
-            else if (s->kind == USB_TABLET)
-                ret = usb_tablet_poll(s, p->data, p->len);
-            else if (s->kind == USB_KEYBOARD)
-                ret = usb_keyboard_poll(&s->kbd, p->data, p->len);
+            if (s->kind == USB_MOUSE || s->kind == USB_TABLET) {
+                ret = usb_pointer_poll(s, p->data, p->len);
+                s->changed = s->ptr.n > 0;
+            }
+            else if (s->kind == USB_KEYBOARD) {
+                ret = usb_keyboard_poll(s, p->data, p->len);
+                s->changed = 0;
+            }
         } else {
             goto fail;
         }
@@ -871,13 +904,13 @@  static int usb_hid_initfn(USBDevice *dev, int kind)
     s->kind = kind;
 
     if (s->kind == USB_MOUSE) {
-        s->ptr.eh_entry = qemu_add_mouse_event_handler(usb_mouse_event, s,
+        s->ptr.eh_entry = qemu_add_mouse_event_handler(usb_pointer_event, s,
                                                        0, "QEMU USB Mouse");
     } else if (s->kind == USB_TABLET) {
-        s->ptr.eh_entry = qemu_add_mouse_event_handler(usb_tablet_event, s,
+        s->ptr.eh_entry = qemu_add_mouse_event_handler(usb_pointer_event, s,
                                                        1, "QEMU USB Tablet");
     }
-        
+
     /* Force poll routine to be run and grab input the first time.  */
     s->changed = 1;
     return 0;