keymap: hash table collisions

Bug #426647 reported by Martin Pitt
8
This bug affects 1 person
Affects Status Importance Assigned to Milestone
udev
Fix Released
Undecided
Martin Pitt
udev (Ubuntu)
Fix Released
Medium
Martin Pitt

Bug Description

Binary package hint: udev

<mezcalero> [22:31:27] pitti: i just ran udev through llvm-clang-analyzer
<mezcalero> [22:32:22] pitti: as it turns out the keymap in the kernel is not bijective
<mezcalero> [22:32:36] pitti: i.e. more than one name are mapped to the same key
<mezcalero> [22:33:08] example: HANGEUL and HANGUEL
<mezcalero> [22:33:26] pitti: now, the perfect hashtable that is generated from that is actually not that perfect due to that
<mezcalero> [22:33:31] and weird things might happen
<mezcalero> [22:33:40] pitti: this probably should be fixed in some way
<mezcalero> [22:33:52] pitti: probably by preprocessing input.h in some and filtering out duplicates
<mezcalero> [22:34:01] and sticking to the first names defined there in case of an ambiguity
<mezcalero> [22:34:11] pitti: just wanted to ping you about that...
<mezcalero> [22:34:57] pitti: http://fpaste.org/t6ow/
<mezcalero> [22:37:31] pitti: the fix is probably as easy as simply filtering KEY_HANGUEL, KEY_COFFEE, KEY_MIN_INTERESTING from the table
<mezcalero> [22:37:53] pitti: because they seem to be irrelevant as real keys

   1.
      In file included from extras/keymap/keymap.c:40:
   2.
      extras/keymap/keys-to-name.h:124:17: warning: initializer overrides prior initialization of this subobject
   3.
      [KEY_HANGUEL] = "KEY_HANGUEL",
   4.
      ^~~~~~~~~~~~~
   5.
      extras/keymap/keys-to-name.h:123:17: note: previous initialization is here
   6.
      [KEY_HANGEUL] = "KEY_HANGEUL",
   7.
      ^~~~~~~~~~~~~
   8.
      extras/keymap/keys-to-name.h:155:20: warning: initializer overrides prior initialization of this subobject
   9.
      [KEY_SCREENLOCK] = "KEY_SCREENLOCK",
  10.
      ^~~~~~~~~~~~~~~~
  11.
      extras/keymap/keys-to-name.h:154:16: note: previous initialization is here
  12.
      [KEY_COFFEE] = "KEY_COFFEE",
  13.
      ^~~~~~~~~~~~
  14.
      extras/keymap/keys-to-name.h:380:25: warning: initializer overrides prior initialization of this subobject
  15.
      [KEY_MIN_INTERESTING] = "KEY_MIN_INTERESTING",
  16.
      ^~~~~~~~~~~~~~~~~~~~~
  17.
      extras/keymap/keys-to-name.h:114:14: note: previous initialization is here
  18.
      [KEY_MUTE] = "KEY_MUTE",
  19.
      ^~~~~~~~~~

Related branches

Martin Pitt (pitti)
Changed in udev (Ubuntu):
assignee: nobody → Martin Pitt (pitti)
importance: Undecided → Medium
status: New → In Progress
Revision history for this message
Martin Pitt (pitti) wrote :

OK, instead of filtering particular keys, I fixed the awk invocation to ignore aliases:

- $(AM_V_GEN)$(AWK) '/^#define.*KEY_/ { if ($$2 != "KEY_MAX" && $$2 != "KEY_CNT") { print $$2 } }' < $< > $@
+ $(AM_V_GEN)$(AWK) '/^#define.*KEY_[^ ]+[[:space:]]+[0-9]/ { if ($$2 != "KEY_MAX") { print $$2 } }' < $< > $@

This changes keys.txt as folllows:

--- keys.txt.old 2009-09-09 10:39:37.000000000 +0200
+++ keys.txt 2009-09-09 11:03:01.000000000 +0200
@@ -120,7 +120,6 @@
 KEY_SCALE
 KEY_KPCOMMA
 KEY_HANGEUL
-KEY_HANGUEL
 KEY_HANJA
 KEY_YEN
 KEY_LEFTMETA
@@ -151,7 +150,6 @@
 KEY_WWW
 KEY_MSDOS
 KEY_COFFEE
-KEY_SCREENLOCK
 KEY_DIRECTION
 KEY_CYCLEWINDOWS
 KEY_MAIL
@@ -376,4 +374,3 @@
 KEY_NUMERIC_9
 KEY_NUMERIC_STAR
 KEY_NUMERIC_POUND
-KEY_MIN_INTERESTING

Thanks for finding this!

Revision history for this message
Martin Pitt (pitti) wrote :

I also adapted the existing keymaps for the removed aliases, distcheck succeeds again.

Committed to http://git.kernel.org/?p=linux/hotplug/udev.git;a=commitdiff;h=6983c0d0f2e396102118016eb7d9dafb3e193d57

Thanks for pointing this out!

Changed in udev:
assignee: nobody → Martin Pitt (pitti)
status: New → Fix Released
Revision history for this message
Martin Pitt (pitti) wrote :

Will go to Ubuntu once 147 is released and uploaded.

Changed in udev (Ubuntu):
status: In Progress → Fix Committed
Revision history for this message
Launchpad Janitor (janitor) wrote :

This bug was fixed in the package udev - 147~-1

---------------
udev (147~-1) karmic; urgency=low

  FFE LP: #427356.

  * Update to GIT HEAD (pre 147 release):
    - worker signal mask corrected. LP: #407428.
    - database format change to avoid path length issues. LP: #377121.
    - multiple devices may not claim the same /dev names, except with
      symlinks
    - NAME="%k" produces a warning
    - symlinks to udevadm no longer resolve to the original command
    - rules updates. LP: #281335, LP: #407940, #420015, #426647.

  * Build-depend on gawk, since build fails with mawk.

  * Replace init scripts with Upstart jobs.
  * debian/control:
    - Add missing ${misc:Depends}
    - Bump build-dependency on debhelper for Upstart-aware dh_installinit

 -- Scott James Remnant <email address hidden> Tue, 15 Sep 2009 03:22:11 +0100

Changed in udev (Ubuntu):
status: Fix Committed → Fix Released
To post a comment you must log in.
This report contains Public information  
Everyone can see this information.

Other bug subscribers

Remote bug watches

Bug watches keep track of this bug in other bug trackers.