Thursday, March 21, 2019

Using hexdump to print binary protocols

I had to work on an image yesterday where I couldn't install anything and the amount of pre-installed tools was quite limited. And I needed to debug an input device, usually done with libinput record. So eventually I found that hexdump supports formatting of the input bytes but it took me a while to figure out the right combination. The various resources online only got me partway there. So here's an explanation which should get you to your results quickly.

By default, hexdump prints identical input lines as a single line with an asterisk ('*'). To avoid this, use the -v flag as in the examples below.

hexdump's format string is single-quote-enclosed string that contains the count, element size and double-quote-enclosed printf-like format string. So a simple example is this:

$ hexdump -v -e '1/2 "%d\n"' 
-11643
23698
0
0
-5013
6
0
0
This prints 1 element ('iteration') of 2 bytes as integer, followed by a linebreak. Or in other words: it takes two bytes, converts it to int and prints it. If you want to print the same input value in multiple formats, use multiple -e invocations.
$ hexdump -v -e '1/2 "%d "' -e '1/2 "%x\n"' 
-11568 d2d0
23698 5c92
0 0
0 0
6355 18d3
1 1
0 0
This prints the same 2-byte input value, once as decimal signed integer, once as lowercase hex. If we have multiple identical things to print, we can do this:
$ hexdump -v -e '2/2 "%6d "' -e '" hex:"' -e '4/1 " %x"' -e '"\n"'
-10922  23698 hex: 56 d5 92 5c
     0      0 hex: 0 0 0 0
 14879      1 hex: 1f 3a 1 0
     0      0 hex: 0 0 0 0
     0      0 hex: 0 0 0 0
     0      0 hex: 0 0 0 0
Which prints two elements, each size 2 as integers, then the same elements as four 1-byte hex values, followed by a linebreak. %6d is a standard printf instruction and documented in the manual.

Let's go and print our protocol. The struct representing the protocol is this one:

struct input_event {
#if (__BITS_PER_LONG != 32 || !defined(__USE_TIME_BITS64)) && !defined(__KERNEL__)
        struct timeval time;
#define input_event_sec time.tv_sec
#define input_event_usec time.tv_usec
#else
        __kernel_ulong_t __sec;
#if defined(__sparc__) && defined(__arch64__)
        unsigned int __usec;
#else
        __kernel_ulong_t __usec;
#endif
#define input_event_sec  __sec
#define input_event_usec __usec
#endif
        __u16 type;
        __u16 code;
        __s32 value;
};
So we have two longs for sec and usec, two shorts for type and code and one signed 32-bit int. Let's print it:
$ hexdump -v -e '"E: " 1/8 "%u." 1/8 "%06u" 2/2 " %04x" 1/4 "%5d\n"' /dev/input/event22 
E: 1553127085.097503 0002 0000    1
E: 1553127085.097503 0002 0001   -1
E: 1553127085.097503 0000 0000    0
E: 1553127085.097542 0002 0001   -2
E: 1553127085.097542 0000 0000    0
E: 1553127085.108741 0002 0001   -4
E: 1553127085.108741 0000 0000    0
E: 1553127085.118211 0002 0000    2
E: 1553127085.118211 0002 0001  -10
E: 1553127085.118211 0000 0000    0
E: 1553127085.128245 0002 0000    1
And voila, we have our structs printed in the same format evemu-record prints out. So with nothing but hexdump, I can generate output I can then parse with my existing scripts on another box.

Friday, March 15, 2019

libinput's internal building blocks

Ho ho ho, let's write libinput. No, of course I'm not serious, because no-one in their right mind would utter "ho ho ho" without a sufficient backdrop of reindeers to keep them sane. So what this post is instead is me writing a nonworking fake libinput in Python, for the sole purpose of explaining roughly how libinput's architecture looks like. It'll be to the libinput what a Duplo car is to a Maserati. Four wheels and something to entertain the kids with but the queue outside the nightclub won't be impressed.

The target audience are those that need to hack on libinput and where the balance of understanding vs total confusion is still shifted towards the latter. So in order to make it easier to associate various bits, here's a description of the main building blocks.

libinput uses something resembling OOP except that in C you can't have nice things unless what you want is a buffer overflow\n\80xb1001af81a2b1101. Instead, we use opaque structs, each with accessor methods and an unhealthy amount of verbosity. Because Python does have classes, those structs are represented as classes below. This all won't be actual working Python code, I'm just using the syntax.

Let's get started. First of all, let's create our library interface.

class Libinput:
   @classmethod
   def path_create_context(cls):
        return _LibinputPathContext()

   @classmethod
   def udev_create_context(cls):
       return _LibinputUdevContext()

   # dispatch() means: read from all our internal fds and
   # call the dispatch method on anything that has changed
   def dispatch(self):
        for fd in self.epoll_fd.get_changed_fds():
           self.handlers[fd].dispatch()

   # return whatever the next event is
   def get_event(self):
        return self._events.pop(0)

   # the various _notify functions are internal API
   # to pass things up to the context
   def _notify_device_added(self, device):
        self._events.append(LibinputEventDevice(device))
        self._devices.append(device)

   def _notify_device_removed(self, device):
        self._events.append(LibinputEventDevice(device))
        self._devices.remove(device)

   def _notify_pointer_motion(self, x, y):
        self._events.append(LibinputEventPointer(x, y))



class _LibinputPathContext(Libinput):
   def add_device(self, device_node):
       device = LibinputDevice(device_node)
       self._notify_device_added(device)

   def remove_device(self, device_node):
       self._notify_device_removed(device)


class _LibinputUdevContext(Libinput):
   def __init__(self):
       self.udev = udev.context()

   def udev_assign_seat(self, seat_id):
       self.seat_id = seat.id

       for udev_device in self.udev.devices():
          device = LibinputDevice(udev_device.device_node)
          self._notify_device_added(device)


We have two different modes of initialisation, udev and path. The udev interface is used by Wayland compositors and adds all devices on the given udev seat. The path interface is used by the X.Org driver and adds only one specific device at a time. Both interfaces have the dispatch() and get_events() methods which is how every caller gets events out of libinput.

In both cases we create a libinput device from the data and create an event about the new device that bubbles up into the event queue.

But what really are events? Are they real or just a fidget spinner of our imagination? Well, they're just another object in libinput.

class LibinputEvent:
     @property
     def type(self):
        return self._type

     @property
     def context(self):
         return self._libinput
       
     @property
     def device(self):
        return self._device

     def get_pointer_event(self):
        if instanceof(self, LibinputEventPointer):
            return self  # This makes more sense in C where it's a typecast
        return None

     def get_keyboard_event(self):
        if instanceof(self, LibinputEventKeyboard):
            return self  # This makes more sense in C where it's a typecast
        return None


class LibinputEventPointer(LibinputEvent):
     @property
     def time(self)
        return self._time/1000

     @property
     def time_usec(self)
        return self._time

     @property
     def dx(self)
        return self._dx

     @property
     def absolute_x(self):
        return self._x * self._x_units_per_mm

     @property
     def absolute_x_transformed(self, width):
        return self._x *  width/ self._x_max_value
You get the gist. Each event is actually an event of a subtype with a few common shared fields and a bunch of type-specific ones. The events often contain some internal value that is calculated on request. For example, the API for the absolute x/y values returns mm, but we store the value in device units instead and convert to mm on request.

So, what's a device then? Well, just another I-cant-believe-this-is-not-a-class with relatively few surprises:

class LibinputDevice:
   class Capability(Enum):
       CAP_KEYBOARD = 0
       CAP_POINTER  = 1
       CAP_TOUCH    = 2
       ...

   def __init__(self, device_node):
      pass  # no-one instantiates this directly

   @property
   def name(self):
      return self._name

   @property
   def context(self):
      return self._libinput_context

   @property
   def udev_device(self):
      return self._udev_device

   @property
   def has_capability(self, cap):
      return cap in self._capabilities

   ...
Now we have most of the frontend API in place and you start to see a pattern. This is how all of libinput's API works, you get some opaque read-only objects with a few getters and accessor functions.

Now let's figure out how to work on the backend. For that, we need something that handles events:

class EvdevDevice(LibinputDevice):
    def __init__(self, device_node):
       fd = open(device_node)
       super().context.add_fd_to_epoll(fd, self.dispatch)
       self.initialize_quirks()

    def has_quirk(self, quirk):
        return quirk in self.quirks

    def dispatch(self):
       while True:
          data = fd.read(input_event_byte_count)
          if not data:
             break

          self.interface.dispatch_one_event(data)

    def _configure(self):
       # some devices are adjusted for quirks before we 
       # do anything with them
       if self.has_quirk(SOME_QUIRK_NAME):
           self.libevdev.disable(libevdev.EV_KEY.BTN_TOUCH)


       if 'ID_INPUT_TOUCHPAD' in self.udev_device.properties:
          self.interface = EvdevTouchpad()
       elif 'ID_INPUT_SWITCH' in self.udev_device.properties:
          self.interface = EvdevSwitch()
       ...
       else:
          self.interface = EvdevFalback()


class EvdevInterface:
    def dispatch_one_event(self, event):
        pass

class EvdevTouchpad(EvdevInterface):
    def dispatch_one_event(self, event):
        ...

class EvdevTablet(EvdevInterface):
    def dispatch_one_event(self, event):
        ...


class EvdevSwitch(EvdevInterface):
    def dispatch_one_event(self, event):
        ...

class EvdevFallback(EvdevInterface):
    def dispatch_one_event(self, event):
        ...
Our evdev device is actually a subclass (well, C, *handwave*) of the public device and its main function is "read things off the device node". And it passes that on to a magical interface. Other than that, it's a collection of generic functions that apply to all devices. The interfaces is where most of the real work is done.

The interface is decided on by the udev type and is where the device-specifics happen. The touchpad interface deals with touchpads, the tablet and switch interface with those devices and the fallback interface is that for mice, keyboards and touch devices (i.e. the simple devices).

Each interface has very device-specific event processing and can be compared to the Xorg synaptics vs wacom vs evdev drivers. If you are fixing a touchpad bug, chances are you only need to care about the touchpad interface.

The device quirks used above are another simple block:

class Quirks:
   def __init__(self):
       self.read_all_ini_files_from_directory('$PREFIX/share/libinput')

   def has_quirk(device, quirk):
       for file in self.quirks:
          if quirk.has_match(device.name) or
             quirk.has_match(device.usbid) or
             quirk.has_match(device.dmi):
             return True
       return False

   def get_quirk_value(device, quirk):
       if not self.has_quirk(device, quirk):
           return None

       quirk = self.lookup_quirk(device, quirk)
       if quirk.type == "boolean":
           return bool(quirk.value)
       if quirk.type == "string":
           return str(quirk.value)
       ...
A system that reads a bunch of .ini files, caches them and returns their value on demand. Those quirks are then used to adjust device behaviour at runtime.

The next building block is the "filter" code, which is the word we use for pointer acceleration. Here too we have a two-layer abstraction with an interface.

class Filter:
   def dispatch(self, x, y):
      # converts device-unit x/y into normalized units
      return self.interface.dispatch(x, y)

   # the 'accel speed' configuration value
   def set_speed(self, speed):
       return self.interface.set_speed(speed)

   # the 'accel speed' configuration value
   def get_speed(self):
       return self.speed

   ...


class FilterInterface:
   def dispatch(self, x, y):
       pass

class FilterInterfaceTouchpad:
   def dispatch(self, x, y):
       ...
       
class FilterInterfaceTrackpoint:
   def dispatch(self, x, y):
       ...

class FilterInterfaceMouse:
   def dispatch(self, x, y):
      self.history.push((x, y))
      v = self.calculate_velocity()
      f = self.calculate_factor(v)
      return (x * f, y * f)

   def calculate_velocity(self)
      for delta in self.history:
          total += delta
      velocity = total/timestamp  # as illustration only

   def calculate_factor(self, v):
      # this is where the interesting bit happens,
      # let's assume we have some magic function
      f = v * 1234/5678
      return f
So libinput calls filter_dispatch on whatever filter is configured and passes the result on to the caller. The setup of those filters is handled in the respective evdev interface, similar to this:
class EvdevFallback:
    ...
    def init_accel(self):
         if self.udev_type == 'ID_INPUT_TRACKPOINT':
             self.filter = FilterInterfaceTrackpoint()
         elif self.udev_type == 'ID_INPUT_TOUCHPAD':
             self.filter = FilterInterfaceTouchpad()
         ...
The advantage of this system is twofold. First, the main libinput code only needs one place where we really care about which acceleration method we have. And second, the acceleration code can be compiled separately for analysis and to generate pretty graphs. See the pointer acceleration docs. Oh, and it also allows us to easily have per-device pointer acceleration methods.

Finally, we have one more building block - configuration options. They're a bit different in that they're all similar-ish but only to make switching from one to the next a bit easier.

class DeviceConfigTap:
    def set_enabled(self, enabled):
       self._enabled = enabled

    def get_enabled(self):
        return self._enabled

    def get_default(self):
        return False

class DeviceConfigCalibration:
    def set_matrix(self, matrix):
       self._matrix = matrix

    def get_matrix(self):
        return self._matrix

    def get_default(self):
        return [1, 0, 0, 0, 1, 0, 0, 0, 1]
And then the devices that need one of those slot them into the right pointer in their structs:
class  EvdevFallback:
   ...
   def init_calibration(self):
      self.config_calibration = DeviceConfigCalibration()
      ...

   def handle_touch(self, x, y):
       if self.config_calibration is not None:
           matrix = self.config_calibration.get_matrix

       x, y = matrix.multiply(x, y)
       self.context._notify_pointer_abs(x, y)

And that's basically it, those are the building blocks libinput has. The rest is detail. Lots of it, but if you understand the architecture outline above, you're most of the way there in diving into the details.

libinput and location-based touch arbitration

One of the features in the soon-to-be-released libinput 1.13 is location-based touch arbitration. Touch arbitration is the process of discarding touch input on a tablet device while a pen is in proximity. Historically, this was provided by the kernel wacom driver but libinput has had userspace touch arbitration for quite a while now, allowing for touch arbitration where the tablet and the touchscreen part are handled by different kernel drivers.

Basic touch arbitratin is relatively simple: when a pen goes into proximity, all touches are ignored. When the pen goes out of proximity, new touches are handled again. There are some extra details (esp. where the kernel handles arbitration too) but let's ignore those for now.

With libinput 1.13 and in preparation for the Dell Canvas Dial Totem, the touch arbitration can now be limited to a portion of the screen only. On the totem (future patches, not yet merged) that portion is a square slightly larger than the tool itself. On normal tablets, that portion is a rectangle, sized so that it should encompass the users's hand and area around the pen, but not much more. This enables users to use both the pen and touch input at the same time, providing for bimanual interaction (where the GUI itself supports it of course). We use the tilt information of the pen (where available) to guess where the user's hand will be to adjust the rectangle position.

There are some heuristics involved and I'm not sure we got all of them right so I encourage you to give it a try and file an issue where it doesn't behave as expected.