OSDev.org

Okay, so I have a basic keyboard interrupt handler set up that simply converts the scancode to an ASCII char via a lookup table and sticks it onto the screen. Next, I would like to develop this into a shell-like environment that can accept commands given by the user. However, before I start to implement the actual shell, I think I need a better way of keeping track of input. In particular, I would like to implement `gets()`.

So far, I think I need to keep a buffer of characters as they are pressed, but I'm not sure whether to store actual scancodes or convert them into something else first (the current ASCII system wouldn't work too well, as I'm not sure how I'd buffer things like ctrl-C). But I don't know what the implementation of gets() would look like - could I just wait in an infinite loop and poll the buffer for a newline character? Seems rather inefficient to me.

Try to be more specific: are you wanting to know how to buffer keyboard input, or how to write a shell? They're not the same thing. The OS buffers the keyboard input; the shell works with the OS to retrieve keys from the buffer.

In a multitasking OS typically a function like "gets" is implemented in a userland library, and reaches into your kernel's hardware abstraction layer to query the keyboard driver. That driver buffers keys as they are pressed using interrupts and waits for a userland program to request them.

However, if you just want to be able to call something like "gets" from your bootloader/kernel work-in-progress code then yes, you could do something as simple as looping until newline.

Can you provide more information about the context? Is this real mode code using legacy BIOS interrupts? Real/protected/long mode code using PIO? Do you have a vision in mind of how you want to abstract hardware from userland programs?

onlyonemac wrote:Try to be more specific: are you wanting to know how to buffer keyboard input, or how to write a shell? They're not the same thing. The OS buffers the keyboard input; the shell works with the OS to retrieve keys from the buffer.

I have an idea on how I want to implement the shell. What I want to know is how to implement an efficient keyboard driver.

intx13 wrote:Can you provide more information about the context? Is this real mode code using legacy BIOS interrupts? Real/protected/long mode code using PIO? Do you have a vision in mind of how you want to abstract hardware from userland programs?

I'm in protected mode, with a working ISR handling IRQ1, which is receiving keyboard input correctly. I have not dabbled in userlands yet, but I guess I'll provide a bunch of system calls back into the kernel at a later date. I was, however, thinking of having the shell run in kernel mode (there is no plan to move away from the shell to a GUI environment or anything), or would it be better to have it as a userland program?

BaconWraith wrote:

onlyonemac wrote: I'm in protected mode, with a working ISR handling IRQ1, which is receiving keyboard input correctly. I have not dabbled in userlands yet, but I guess I'll provide a bunch of system calls back into the kernel at a later date. I was, however, thinking of having the shell run in kernel mode (there is no plan to move away from the shell to a GUI environment or anything), or would it be better to have it as a userland program?

Shells are usually run as userland processes. If you're planning on setting up a userland environment, it might be a good opportunity to do so. Then you can write a library providing gets() which reaches out to your keyboard driver.

As for how your keyboard driver buffers, that's up to you. You could keep a fixed-length buffer and add events to it, rolling them off the back-end as it fills up. You could store scan codes, or you could let your userland program tell the driver which key map to use, and then the driver stores decoded key presses.

At this stage, a simplified rump shell or even a single-character menu running in kernel space would be advisable for testing the kernel and drivers, before jumping into the actual full shell development. Going to a full shell before the rest of the system is debugged would probably be premature.

One option that would let you experiment with the shell design now would be to mock it up on your development host, keeping those parts of it that are OS-specific separate from the shell itself, as this would give you a chance to crystallize your design while you are still working out the details of the kernel interface.

Whether you decide to run the 'real' version of the shell in kernel space or user space is your call, though it is more commonly run in userland for protection and crash isolation.

One thing I would recommend is to mark the kernel space console operations in some way so that they are easily differentiated from the equivalent standard library functions, e.g., naming the string reading function kgets() or get_console_str(). That should help avoid confusion later.

Also, the standard gets() is deprecated (as you probably know) and has been removed in the latest version of the standard; the reason for this is that the standard function as originally defined had no bounds checking, and thus was the source of many of the buffer overruns that have plagued Unix and Windows programs for decades. You will almost certainly want to include bounds checking in you function, whether implicitly (i.e., the function simply won't read more than a certain amount from the input at once, or uses a ring buffer) or explicitly (requiring a buffer pointer and maximum size to be passed to it, as with fgets()). This is especially important inside the kernel, so you will want to work that out in detail and write down what you decide to do so that you don't get confused on the point later.

Hi,

Scan codes are annoying (e.g. you can't use them for array indexes); so at the lowest level you want some sort of state machine that converts the keyboard's scan codes into nice "key codes". You want to send key codes plus a "pressed/released" flag to the next stage.

The next stage is an array of bits (one for each key code) that keeps track of whether the key is current being pressed or not. This is needed for special keys (control, alt, shift) but can also be useful for other purposes. If the key was released clear the corresponding bit. If the key was pressed set the corresponding bit. At this point you can detect if it's a "repeated key" (was already pressed beforehand) and discard it if it is - it's more fun to emulate "key repeat" in software if/when its needed because this is more flexible and also more consistent (because normally some keys repeat and others don't). After this you want to send the key code, plus either "pressed/repeated/released" status (if you're using the keyboard's "key repeat") or "pressed/release" status, plus some more flags (left and right shift, control, alt key states), plus LED (num-lock/caps-lock/scroll-lock) states to the next stage.

For keyboards there's a lot of different keyboard layouts (the wikipedia page only shows the most common ones). The next stage deals with this using tables (aren't you glad you're use a nice "key code" for array indexes?); where the table for current keyboard layout is loaded from disk and depends on what the keyboard says it is (for USB only, unless it says "US qwerty" which often means "keyboard manufacturer too lazy to get it right") or based on the user's preferences. This is where you find the unicode character for the key, if any. Don't use ASCII (it's useless/obsolete and should've been banned 30 years ago). After this you want to send the key code, "pressed/repeated/released" status, shift/control/alt key states, LED states and the character (if any) to the next stage. We'll call this a "key press event". Note that at the lowest level you could've started with a "key press event" with half the information missing, and then just added the missing information as you go through the stages.

The next stage is optional. It's an [url=https://en.wikipedia.org/wiki/Input_method]"input method editor". For some languages (e.g. Japanese) to have one key per character you'd need a massive keyboard with thousands of keys; so to work around that you use a piece of software to assist the user choose the character they actually want. You can think of this like a "man in the middle" that converts key press events from the previous stage into other key press events for the next stage. If there's no input method editor then you those key press events go directly to the next stage. This should probably be done in user-space.

The last stage is whatever you want it to be. It could be a virtual terminal layer or TTY that handles "control+alt+delete" and switching between termainls and then strips all the good/useful information out and shoves the shrapnel down a pipe (like STDIN); or it could be something more like a GUI or computer game or whatever. This is all user-space.

Note that everywhere where I've said "sends to the next stage" you have a choice of using (e.g.) function calls or some sort of communication (pipes, messages, fifo buffer, etc). In general you want to keep the interrupt handler itself small, which means using some sort of communication between the interrupt handler and the rest of the keyboard driver. You'll also need some sort of communication to talk to user-space and between different processes in user-space.


Cheers,

Brendan

BaconWraith wrote:

onlyonemac wrote:Try to be more specific: are you wanting to know how to buffer keyboard input, or how to write a shell? They're not the same thing. The OS buffers the keyboard input; the shell works with the OS to retrieve keys from the buffer.

I have an idea on how I want to implement the shell. What I want to know is how to implement an efficient keyboard driver.

OK. Basically, your keyboard driver takes the scancodes from the keyboard, converts them to ASCII (or Unicode, depending on the operating system, but you said you were using ASCII so that's fine) and stores them in a buffer. Then when something wants to get a key from the keyboard driver, it says to the driver "give me the next character that was entered" and the driver gives it the oldest character in the buffer and removes it from the buffer.

There are different ways of implementing this buffer, but a common method is a "circular buffer" whereby an area of memory is allocated for the buffer, and two pointers are kept: one pointer points to the start of the buffer (the location where the oldest character is stored) and the other pointer points to the end of the buffer (the location where the next character will be stored). When a key is pressed, the character is stored at the location of the latter pointer and the pointer is incremented; when a character is requested by a program, the character is read from the location of the former pointer and the pointer is incremented. When either pointer reaches the end of the buffer, the pointer is wrapped around to the start of the buffer. When the buffer gets full (the end pointer wraps round until it is equal to the start pointer), the action taken depends on the OS but will usually either be to discard the oldest character or to ignore all subsequent characters - I'm not sure which is more common and/or better.

Your keyboard driver might also keep a few other pieces of information about the keyboard, such as a bitmap of which keys are pressed so that an application can say "is ... key currently pressed?" which is useful for programs such as games which work not on a character-by-character basis but rather a key-by-key basis.

Okay, thanks everyone for your feedback. It's clear that I need to concentrate on getting the keyboard driver done first, as I would like to do the shell properly and have it in run in userland.

The idea of the circular buffer is one I hadn't thought about, and I think I'll go with it, so thanks onlyonemac!

Brendan wrote:This is where you find the unicode character for the key, if any. Don't use ASCII (it's useless/obsolete and should've been banned 30 years ago).

What's the problem with ASCII? Certainly for the moment, I plan to only support English and my video driver only supports ASCII to create VGA entries anyway?

Hi,

BaconWraith wrote:

Brendan wrote:This is where you find the unicode character for the key, if any. Don't use ASCII (it's useless/obsolete and should've been banned 30 years ago).

What's the problem with ASCII? Certainly for the moment, I plan to only support English and my video driver only supports ASCII to create VGA entries anyway?

The problem with ASCII is that it only supports a sub-set of English and fails completely for almost every other language, including maths (e.g. 3×4÷5 ≠ 3x4/5).

The problem with "for the moment" is that at the moment you're designing something that more and more software will depend on as time passes, which means that the longer it takes before you fix the mistake the harder it becomes to fix the mistake, and something that could've been fixed/avoided in less than 1 minute can takes weeks to fix later on.

Just because your keyboard driver is designed to handle Unicode doesn't mean it has to have full Unicode support immediately. The most important thing is (e.g.) using something like "uint32_t codepoint;" instead of "char ASCII_char;" in the data structures and protocols used for "key press packets" and for the tables the driver uses to support different keyboard layouts properly; so that it is easy to increase/improve Unicode support in one piece without changing the data structures used by multiple pieces.

Note that none of this has anything to do with displaying the characters. You could have full Unicode support throughout the entire OS (including keyboard driver, keyboard layouts, input method editors, file systems and file names, etc); but still only have a video driver that only supports ASCII (and displays an inverted '?' character or something when it can't display a character correctly). Also; don't forget that VGA text mode (which is also obsolete and should've been banned 30 years ago) in not ASCII but is actually code page 437; which means that with a simple "Unicode to code page 437" conversion VGA text mode can correctly display more of the characters that are used by a lot of languages (English, Spanish, German, ....).


Cheers,

Brendan

Right. Simply replace char with uint32.

Not all graphemes (fancy word for letter) fit into one code point, because https://en.wikipedia.org/wiki/Combining_character do exist. So, you might want to use an array of code points in the encoding of your choice.

Or only support precombined ones. That wouldn't be too bad, because most of the time users won't have 'x with circle' on their keyboard but a key for 'put a circle over the next character', which emits the corresponding combining character.

Hi,

HoTT wrote:Not all graphemes (fancy word for letter) fit into one code point, because https://en.wikipedia.org/wiki/Combining_character do exist. So, you might want to use an array of code points in the encoding of your choice.

Or only support precombined ones. That wouldn't be too bad, because most of the time users won't have 'x with circle' on their keyboard but a key for 'put a circle over the next character', which emits the corresponding combining character.

I'm "linguistically impaired" (I only know and only use English, which puts me at a major disadvantage for anything involving internationalisation); but as far as I know for most (all?) cases involving combining characters that don't require an input method editor the user presses 2 or more keys (e.g. one key to get the base character and then a second key to add a diacritical mark); and if cases do exist where a single key press should cause 2 or more code-points the keyboard driver could just send 2 or more key press packets.


Cheers,

Brendan

I'm "linguistically impaired" (I only know and only use English, which puts me at a major disadvantage for anything involving internationalisation); but as far as I know for most (all?) cases involving combining characters that don't require an input method editor the user presses 2 or more keys (e.g. one key to get the base character and then a second key to add a diacritical mark); and if cases do exist where a single key press should cause 2 or more code-points the keyboard driver could just send 2 or more key press packets.

AFAIK, that is correct. The only way to have a grapheme that uses more than one codepoint involves combining characters and if one of your users insists of having a key that is labelled with 'o with circle above, accent below, and solidus overlay' you can generate 4 key presses for that, one for the 'o' and three for the combining characters. I kinda feel like that this might be an awkward model. E.g you cannot count the key presses by counting the key press packets any more. When I configure shortcuts with this scheme, will my shortcut editor think that I press 4 different keys simultaneously? What's with games, when this key should be the one to move my avatar forward but the game developer didn't allow key combinations for basic movement?

I do have a similar thought about modifier keys. Putting that into the kernel/basic driver feels wrong, because it is inherently insufficient. On my keyboard layout I distinguish between left and right shift, control, alt. I have modifiers on shift, left control, capslock and the key next to the big enter key, giving me access to six levels per key. That's wasn't too easy to configure (fortunately others maintain the drivers). Qt got that wrong for years, because having multiple additional modifiers didn't work well with QKeyEvent and some mismatch between XKeyboard and QKeyEvent.

Hi,

HoTT wrote:AFAIK, that is correct. The only way to have a grapheme that uses more than one codepoint involves combining characters and if one of your users insists of having a key that is labelled with 'o with circle above, accent below, and solidus overlay' you can generate 4 key presses for that, one for the 'o' and three for the combining characters. I kinda feel like that this might be an awkward model. E.g you cannot count the key presses by counting the key press packets any more. When I configure shortcuts with this scheme, will my shortcut editor think that I press 4 different keys simultaneously? What's with games, when this key should be the one to move my avatar forward but the game developer didn't allow key combinations for basic movement?

This (and other reasons) is why the key press packet includes the original "key code" (plus other state - pressed/released, etc) and isn't just a character or code-point alone. Something like a game or shortcut editor might only use the key codes.

I'd actually be tempted to go one step further; and define the key code as the physical location of the key (e.g. "code = row * 32 + column") so that (e.g.) a game can use "row 2, column 2". This would require an extra table (to determine the physical location of the key from its scan code); so it'd be a bit messier. You'd probably also want to provide some sort of "find key description from key code" functionality; so that a game can display which key does what in its help system (and can figure out if the key at "row 2, column 2" is 'W' (QWERTY) or 'Z' (AZERTY) or ',' (Dvorak) or 'В' (Russian) or ...).

The other thing that might be worth mentioning is that (eventually) you're going to want some sort of utility that people can use to create "keyboard layout files".

Lastly; I'd worry about security (key loggers). I wouldn't want to allow something like an input method editor to be able to use the network.

HoTT wrote:A do have a similar thought about modifier keys. Putting that into the kernel/basic driver feels wrong, because it is inherently insufficient. On my keyboard layout I distinguish between left and right shift, control, alt. I have modifiers on shift, left control, capslock and the key next to the big enter key, giving me access to six levels per key. That's wasn't too easy to configure (fortunately others maintain the drivers). Qt got that wrong for years, because having multiple additional modifiers didn't work well with QKeyEvent and some mismatch between XKeyboard and QKeyEvent.

I'd just combine the LED states, the states of all modifier keys and the key code together to create an index into a lookup table. With 3 LEDs, 6 modifiers and 8-bit key code you'd end up with a 32768 entry lookup table (128 KiB for 32-bit entries) to determine the code point.


Cheers,

Brendan