Keyboard handling: A question about efficiency

Discussions on more advanced topics such as monolithic vs micro-kernels, transactional memory models, and paging vs segmentation should go here. Use this forum to expand and improve the wiki!
Post Reply
psychobeagle12
Member
Member
Posts: 41
Joined: Wed Oct 26, 2011 9:31 am

Keyboard handling: A question about efficiency

Post by psychobeagle12 »

So I am still in the (very) early stages of developing a basic kernel. I am on a basic ps2 keyboard driver at the moment. I have hooked interrupt 0x21 (my PIC is remapped to 0x20) and am receiving keypresses and handling them in a manner that is working. Not really working without a glitch, but working. Only problem is the input seems unresponsive to me, even on real hardware. I think I can do better. Right now, I am doing something like the following:

1. The interrupt handler (written in ASM) requests the scan code from the keyboard
2. The handler calls a C routine that checks and logs the scan code in a couple of ways

The C routine looks like this:

Code: Select all

void kb_handle_keypress (unsigned int scancode) {

      // process codes by scancode set

     if (scanset == SCANSET_ONE) {

           bool breakcode = false;

           // was a break code sent?
           if (scancode & SETONE_BREAKCODE_MASK) {

                breakcode = true;
                scancode &= ~SETONE_BREAKCODE_MASK;
           }

           // was this an extended scancode?
           if (scancode == SETONE_EXTENDED_SCANCODE || scancode == SETONE_EXTENDED2_SCANCODE) {

                extended = true;
                return;
           }

           // look up the keycode in the keycode maps
           unsigned int keycode = KEYCODE_UNKNOWN;

           // use the uppercase mapping if caps lock is enabled or shift key is down
           if (shift || caps_lock)
                keycode = SCANCODE_SET_ONE_UPPER[scancode];
           else
                keycode = SCANCODE_SET_ONE_LOWER[scancode];

           // if the scancode is a shift key, toggle the shift state
           if (keycode == KEYCODE_LSHIFT || keycode == KEYCODE_RSHIFT)
                shift = (shift) ? false : true;

          // if the caps-lock key was released, toggle the caps-lock state
          if (keycode == KEYCODE_CAPSLOCK && breakcode) {

                caps_lock = (caps_lock) ? false : true;
                kb_set_leds (num_lock, caps_lock, scroll_lock);
          }

          // if a break code was issued, try to place the character in the key queue
          if (breakcode) {

                // if the key is not something like caps lock, scroll lock, ctrl, etc. add it's char equivalent to the queue
                if (!_kb_is_modifier_key (keycode)) {

                      keybuffer[curpos++] = (unsigned char) keycode;

                      // on buffer overflow, cut one character from the queue
                      if (curpos >= KEYBUFFER_MAX)
                           kb_get_keychar ();
                }
          }
     }

     // TODO: Add processing for other scancode sets.
}
Is this too much stuff to be going on inside the interrupt handler? I was considering using a bitmap approach to flag whether a key is down or up, combined with a scancode queue instead of a character queue that would allow me to enter and exit the interrupt quickly. The bitmap would be used to determine which keys are down at any given moment, and the scancode queue would allow me to fetch keys in the order in which they were pressed. Again, this code is working as-is, though every now and then I get a glitch (pressing the GUI keys gives me an odd character, and if I press them twice the driver locks up.) So, my question is, should I be trying a different approach here I suppose. Thoughts?

Edit: I put this in the theory section because I felt it was related to a design choice. If this is in the wrong forum, I apologize and if it can be moved / should be moved please let me know! Also, this code is not anywhere near finished, so any major flaws are yet to be worked out. I just don't want to keep going with the current design choice if it is a poor one.
My i386-based kernel: https://github.com/bmelikant/missy-kernel
Picking a name for my kernel was harder than picking my wife, so I just used her name until I decide!
User avatar
Brendan
Member
Member
Posts: 8561
Joined: Sat Jan 15, 2005 12:00 am
Location: At his keyboard!
Contact:

Re: Keyboard handling: A question about efficiency

Post by Brendan »

Hi,
psychobeagle12 wrote:Is this too much stuff to be going on inside the interrupt handler?
Yes, and no. For example, setting keyboard LEDs shouldn't be done in the interrupt handler. Apart from that, I see no reason why the interrupt handler's code would be too slow.
psychobeagle12 wrote:I was considering using a bitmap approach to flag whether a key is down or up, combined with a scancode queue instead of a character queue that would allow me to enter and exit the interrupt quickly. The bitmap would be used to determine which keys are down at any given moment, and the scancode queue would allow me to fetch keys in the order in which they were pressed. Again, this code is working as-is, though every now and then I get a glitch (pressing the GUI keys gives me an odd character, and if I press them twice the driver locks up.) So, my question is, should I be trying a different approach here I suppose. Thoughts?
In general; I'd suggest that the keyboard IRQ handler should only convert the scancode into a standard "key code" and send the resulting key code to something else (a kernel thread, a "bottom half interrupt handler", whatever).

That "something else" would (e.g.) keep track of the state of each key, convert key codes into "keypress packets" (e.g. including using tables for whatever keyboard layout the user happens to be using to determine the Unicode code point, if any), handle keyboard LEDs, etc. Also, because you'd be using standardised "key codes" (rather than device specific scan codes) the same "something else" could be used by (e.g.) a USB keyboard driver and a PS/2 keyboard driver.

Also note that (at least in my opinion) it's strange for the same PS/2 keyboard driver to handle different scan code sets. More likely the "PS/2 controller driver" would try to disable the scancode translation, then it would use "identify device" to determine what sort of device is present on each PS/2 port (keyboard, mouse, bar-code scanner, touch-pad, whatever); then it would either starts a "no scan-code translation PS/2 keyboard driver" (which sets scan-code set 2 and only ever cares about scan-code set 2), or starts a different/separate "with scan-code set translation PS/2 keyboard driver" (which sets scan-code set 2, and only ever cares about scan-code set 1, because the PS/2 controller is converting from scan-code set 2 back into scan-code set 1).

Note: The PS/2 controller is mostly just a serial port controller with 2 serial ports (where "PS/2" is just a serial communication protocol, similar to RS232 but different). There is nothing preventing you from having (e.g.) a PS/2 keyboard in each port, or a PS/2 mouse in each port, or a special PCI card that provides additional PS/2 ports so you can have 4 PS/2 keyboards at the same time.


Cheers,

Brendan
For all things; perfection is, and will always remain, impossible to achieve in practice. However; by striving for perfection we create things that are as perfect as practically possible. Let the pursuit of perfection be our guide.
psychobeagle12
Member
Member
Posts: 41
Joined: Wed Oct 26, 2011 9:31 am

Re: Keyboard handling: A question about efficiency

Post by psychobeagle12 »

Thanks for the reply! Lots of good info to go on there! Incidentally, I wanted to make my driver by default disable the XT emulation, but I could not for the life of me figure that part out. Does disabling the emulation involve the keyboard's set scanset command? I tried that and failed miserably. I also agree about writing a separate ps2 driver with a "keyboard" layer on top to handle keyboard input. I am definitely going to make this happen as I develop my system. Right now I am trying to learn how the different controllers work, so (I know this is a bad thing) I am writing code for results. I am basically trying to do things simple to learn. I have plans to create a solid system plan and change most of this stuff around after I get a solid idea of the concepts. I want to get some books, but in the meantime I'm mainly trying to learn and have some fun!
My i386-based kernel: https://github.com/bmelikant/missy-kernel
Picking a name for my kernel was harder than picking my wife, so I just used her name until I decide!
User avatar
Brendan
Member
Member
Posts: 8561
Joined: Sat Jan 15, 2005 12:00 am
Location: At his keyboard!
Contact:

Re: Keyboard handling: A question about efficiency

Post by Brendan »

Hi,
psychobeagle12 wrote:Thanks for the reply! Lots of good info to go on there! Incidentally, I wanted to make my driver by default disable the XT emulation, but I could not for the life of me figure that part out. Does disabling the emulation involve the keyboard's set scanset command? I tried that and failed miserably.
The scan-code translation is done by the PS/2 controller. It's controlled by bit 6 in the PS/2 controller configuration byte.

Note that the hardware really is 2 separate devices - the PS/2 controller (which is mostly just a strange serial port controller), and the PS/2 keyboad. This means it's possibly best to think of it as 2 completely separate types of device drivers - one for the PS/2 controller (e.g. that uses IO ports, etc. to send/receive bytes on each serial port), and one for each type of device attached to each serial port (that talks to the PS/2 controller driver asking it to send/receive bytes to its device). In this case, the PS/2 keyboard driver should work fine "as is" when the PS/2 controller is something radically different.

This is similar to USB, where you'd have a USB controller driver (which might be OHCI or UHCI or EHCI or xHCI), plus different device drivers for different USB devices (one for USB keyboard, one for USB flash, one for USB coffee cup warmer, etc); where the USB keyboard driver doesn't really need to know or care what sort of controller it is, and where the controller doesn't necessarily need to know or care what the USB device is.

For the PS/2 controller driver; I'd begin with resetting, self testing and initialising; then do "device auto-detection" (where the PS/2 controller driver is responsible for figuring out which device driver to use for each PS/2 port and starting the appropriate driver for each PS/2 port). The "initialisation" part would include disabling the scan-code translation; and would need to happen before device auto-detection (because the scan-code translation causes irreversible data corruption if/when the device isn't a keyboard using scan-code set 2).

Note that for "hot-plug PS/2" the PS/2 controller's driver may monitor the serial ports; and tell the old device's driver to terminate when the device is unplugged; and do the "device auto-detection" (including starting a device driver) whenever a device is plugged back in.

Finally; don't forget that for decent PS/2 controller initialisation you have to disable "PS/2 emulation for USB devices" first. Typically the firmware's emulation is extremely bad and can't handle it.


Cheers,

Brendan
For all things; perfection is, and will always remain, impossible to achieve in practice. However; by striving for perfection we create things that are as perfect as practically possible. Let the pursuit of perfection be our guide.
psychobeagle12
Member
Member
Posts: 41
Joined: Wed Oct 26, 2011 9:31 am

Re: Keyboard handling: A question about efficiency

Post by psychobeagle12 »

I have definitely given much consideration to getting a working usb driver up next, and that is most likely going to be my next step. I suppose I was going more for results than correctness, and I plan to fix that. I think I understand what you mean with the ps2 driver. So I should do something like:

1. Initialize the PS2 controller
2. Ask the controller about attached devices
3. For each attached device, start a separate driver

So really the main job of the PS2 driver is to initialize devices, then it is really only used when one of the PS2 devices needs to communicate with the controller? Again, driver interaction is something I am still tossing around in my head. Time to get some good books... Thanks for the help though, I truly appreciate it!
My i386-based kernel: https://github.com/bmelikant/missy-kernel
Picking a name for my kernel was harder than picking my wife, so I just used her name until I decide!
User avatar
KemyLand
Member
Member
Posts: 213
Joined: Mon Jun 16, 2014 5:33 pm
Location: Costa Rica

Re: Keyboard handling: A question about efficiency

Post by KemyLand »

psychobeagle12 wrote:So really the main job of the PS2 driver is to initialize devices, then it is really only used when one of the PS2 devices needs to communicate with the controller? Again, driver interaction is something I am still tossing around in my head. Time to get some good books... Thanks for the help though, I truly appreciate it!
What you call "driver interaction" is really called a "driver stack". In a driver stack, every driver does a specific function, and only that function (don't be too modulated here :wink: ). The lowest drivers in the stack manage the most hardware-specific functions, meanwhile the highest drivers manage the most portable and higher-level function. Thus, we can imagine a driver stack with three elements as an example for PS/2 stuff. The lowest driver is the PS/2 Controller driver. It handles device initialization and commands proper to the controller. For each device the driver finds (let's say 2), it "pushes" a new instance of the corresponding driver into the stack. Thus, two new drivers are initialized. Let's say they're the Keyboard driver and the Mouse driver. Both of them are machine independent! The PS/2 Controller driver is the one responsible for coverting scan codes into standard codes. So, once a key is pressed, and the corresponding IRQ redirects to the PS/2 driver, the PS/2 driver computes the standard code. The result is sended as a data packet to the Keyboard driver, which is responsible for advertising the *whole* system about the event. It could also take note of which keys are currently pressed. A bit-array (*not* a byte-array), can help you save memory, with a little computation overhead.

You could have, for example, a GUI daemon over the keyboard and mouse drivers which waits for keypresses and clicks to happen. Once that happens, the keyboard/mouse driver informs the daemon. This exposes another functionality of driver stacks. A good driver *always* reports events upwards in the stack.
Happy New Code!
Hello World in Brainfuck :D:

Code: Select all

++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.
[/size]
psychobeagle12
Member
Member
Posts: 41
Joined: Wed Oct 26, 2011 9:31 am

Re: Keyboard handling: A question about efficiency

Post by psychobeagle12 »

I'm really sorry to bump my own (and incredibly old) post, but I have another question derived from the answers to this question so I didn't want to start another entire post over it. When last I was here we discussed a "driver stack." Now I understand that drivers in the stack basically initialize each other. I am having trouble with understanding a few things about the process. These are my questions regarding driver stacks:

1. I would assume that the initial driver installation process should be started by the kernel. Would the kernel start with installing the highest level drivers to lowest, or lowest to highest (example: virtual terminal driver -> keyboard -> ps/2 controller vs. ps/2 controller -> keyboard -> virtual terminal) In some ways the first seems to make more sense (installing the virtual terminal driver creates the need for a keyboard, the keyboard needs a controller to function, etc.) but in some the second makes sense (when initializing the PS/2 controller we discover a keyboard is attached and start a keyboard driver.) This is probably the biggest hang-up I have to actually implementing a working driver stack.

2. I'm not really sure about the second question. I guess the best approximation is how does the kernel go about loading drivers from a disk when no driver yet exists for the disk? I mean I would suppose that after the system is initially configured you could have a modules file that specifies which disk is the boot disk and which driver it requires and load it in the bootloader, but if the system doesn't have a configuration file how do you decide?

I'm sure there are other questions as well but I started typing my first one and now I don't remember them. So hopefully as this discussion continues (please! :D ) I will be able to remember my questions and ask them. I feel like I am missing something fairly obvious here, so feel free to issue a quick slap if it is necessary. Thanks!
My i386-based kernel: https://github.com/bmelikant/missy-kernel
Picking a name for my kernel was harder than picking my wife, so I just used her name until I decide!
alexfru
Member
Member
Posts: 1111
Joined: Tue Mar 04, 2014 5:27 am

Re: Keyboard handling: A question about efficiency

Post by alexfru »

I remember that setting LEDs wasn't instantaneous and needed some time. Other than that, it may be some issue with scheduling.
FallenAvatar
Member
Member
Posts: 283
Joined: Mon Jan 03, 2011 6:58 pm

Re: Keyboard handling: A question about efficiency

Post by FallenAvatar »

psychobeagle12 wrote:1. I would assume that the initial driver installation process should be started by the kernel. Would the kernel start with installing the highest level drivers to lowest, or lowest to highest (example: virtual terminal driver -> keyboard -> ps/2 controller vs. ps/2 controller -> keyboard -> virtual terminal) In some ways the first seems to make more sense (installing the virtual terminal driver creates the need for a keyboard, the keyboard needs a controller to function, etc.) but in some the second makes sense (when initializing the PS/2 controller we discover a keyboard is attached and start a keyboard driver.) This is probably the biggest hang-up I have to actually implementing a working driver stack.
You do it in the same way as the hardware is "defined". You detect a PS/2 controller, load that driver and that driver will load (or request the kernel load) additional drivers for the devices it detects. This will let you support 2 keyboard, 2 mice, or 1 and 1, or etc.
psychobeagle12 wrote:2. I'm not really sure about the second question. I guess the best approximation is how does the kernel go about loading drivers from a disk when no driver yet exists for the disk? I mean I would suppose that after the system is initially configured you could have a modules file that specifies which disk is the boot disk and which driver it requires and load it in the bootloader, but if the system doesn't have a configuration file how do you decide?
You either hardcode your kernel to support 1 filesystem (and always boot from it), you hardcode it to load a file system driver from a given "HD" sector, or you use some sort of configuration file to determine what to load in your bootloader and pass it to your kernel (Interface pointer would be the best phrase i can come up with to describe it)

- Monk
psychobeagle12
Member
Member
Posts: 41
Joined: Wed Oct 26, 2011 9:31 am

Re: Keyboard handling: A question about efficiency

Post by psychobeagle12 »

So then it would be reasonable to conclude that my kernel should begin by scanning the PCI bus to determine what devices are present. It would start a driver for each device that was present on the bus, and any devices that require sub-devices to be installed (i.e. a PS/2 driver has a keyboard and a mouse attached) would start a driver for each of those. Does this sound about right? So to initialize the keyboard on a system with a PS/2 controller:

scan PCI bus finds PS/2 controller -> ps/2 controller initialization code finds keyboard on first port -> keyboard controller gets initialized (character device)

This question is not related to my OS, but to *nix systems. What sort of device is a controller like a PS/2 controller? Is it considered a character device, and if so, how does the system interact with these devices? How, for example, can a Linux system change the status of the keyboard LEDs? I'm not sure if that question will make sense or not. If not, I can try to clarify!
My i386-based kernel: https://github.com/bmelikant/missy-kernel
Picking a name for my kernel was harder than picking my wife, so I just used her name until I decide!
Ready4Dis
Member
Member
Posts: 571
Joined: Sat Nov 18, 2006 9:11 am

Re: Keyboard handling: A question about efficiency

Post by Ready4Dis »

I think the most common way to load your disk driver and OS is to start with an initial ram disk (Basically a file that loads on bootup that contains all the required drivers to boot the rest of the OS, possibly with a config file). The init ram disk would contain the correct disk driver and file system driver at the very least. Of course, there isn't a right or wrong way (ok, I take that back, a wrong way would be something that doesn't work).

Me personally, I have an initial ram disk that is loaded at the same time as the kernel (kernel is actually a file in the init rd) with a config file that lists the drivers to load in the order I want to load them. I am not completely settled on all the specifics yet, but it works ok for now. There is more than one way to load drivers: You can store a list of PID/VID's that each driver can handle, and when you discover a new device, load the correct driver. You could have a driver stub that you can call and ask if it supports a specific piece of hardware, or ask it to scan for hardware. The other is, if you can't find a piece of hardware by yourself, you may need to load a driver in the first place. For example, one of the first drivers I start is my PCI driver. Without it, not much is going to be found ;). My kernel doesn't know what a serial port is, or how to access it, so I must start my serial port driver for it to scan for valid ports. Anything I find on the PCI bus, I can find a driver for using one of the previously mentioned methods.

Also, your keyboard handler should not be worrying about alt/ctrl/shift/caps... it really just needs to send the data into a buffer/queue and then it should be processed outside of the IRQ, although I can't see why it would be that slow.
psychobeagle12
Member
Member
Posts: 41
Joined: Wed Oct 26, 2011 9:31 am

Re: Keyboard handling: A question about efficiency

Post by psychobeagle12 »

I gave up on worrying about the speed of the keyboard handler lol. I will take care of that when I rewrite the driver for the PS/2 controller and keyboard controller. So then your kernel IS aware of the PCI bus and does know how to work with the PCI bus? So there is no specific PCI bus driver? I would assume that you could also handle this by making the PCI driver part of the initrd and load it's instance as soon as the system starts. I'm just having a problem overall with the logic of drivers for some reason. I did get books since the last time I was here (two of Tanenbaum's books, OS Design and Implementation and another) but I guess something just isn't clicking for me. I appreciate help because this is, for one reason or another, a difficult matter for me to understand. Thank you!
My i386-based kernel: https://github.com/bmelikant/missy-kernel
Picking a name for my kernel was harder than picking my wife, so I just used her name until I decide!
Ready4Dis
Member
Member
Posts: 571
Joined: Sat Nov 18, 2006 9:11 am

Re: Keyboard handling: A question about efficiency

Post by Ready4Dis »

psychobeagle12 wrote:I gave up on worrying about the speed of the keyboard handler lol. I will take care of that when I rewrite the driver for the PS/2 controller and keyboard controller. So then your kernel IS aware of the PCI bus and does know how to work with the PCI bus? So there is no specific PCI bus driver? I would assume that you could also handle this by making the PCI driver part of the initrd and load it's instance as soon as the system starts. I'm just having a problem overall with the logic of drivers for some reason. I did get books since the last time I was here (two of Tanenbaum's books, OS Design and Implementation and another) but I guess something just isn't clicking for me. I appreciate help because this is, for one reason or another, a difficult matter for me to understand. Thank you!
No, my configuration file is aware of a pci bus driver file that it needs to load... my kernel knows nothing about the PCI bus, or any other bus for that matter. If I decide to put it on a system with no PCI bus, but some other bus (legacy ISA bus?), I simply change my configuration file to load (write?) a particular driver for that bus.
psychobeagle12
Member
Member
Posts: 41
Joined: Wed Oct 26, 2011 9:31 am

Re: Keyboard handling: A question about efficiency

Post by psychobeagle12 »

That leads me to another question. How would your operating system then load a driver for the PCI bus on a system for which it wasn't configured? For instance, you got a new laptop and popped the live usb stick in to install your OS. How would your OS know how to boot to that system that could have any kind of bus available? Obviously you would know to use an install for a certain platform, like x86, so would you just load all the drivers for all the possible bus types on that system (for instance, on an x86 you would load the ISA bus driver AND the PCI driver)? And in that way detect which is available by calling the driver initialization routine (telling you for instance that no PCI bus was found when attempting to start the PCI driver)? Does this sound about right?
My i386-based kernel: https://github.com/bmelikant/missy-kernel
Picking a name for my kernel was harder than picking my wife, so I just used her name until I decide!
Ready4Dis
Member
Member
Posts: 571
Joined: Sat Nov 18, 2006 9:11 am

Re: Keyboard handling: A question about efficiency

Post by Ready4Dis »

My PCI bus driver is a driver that is called every time. It may not find any hardware or even find that no PCI bus exists and exit. For a live CD/usb/whatever it would just run it encase it does exist. If it doesn't, no harm no foul, just slowed the bootup process down slightly. I am in the process of re-writing, but this is why I start all AP's before loading all my drivers, so I can multi task my drivers loading. I just have to figure out a good way to make sure if one relies on another that it waits until it's started.
Post Reply