Write a Shell in C (2015)
brennan.io
brennan.io
https://github.com/oilshell/oil/
And a blog here: http://www.oilshell.org/ (index: http://www.oilshell.org/blog/2016/11/20.html)
This article is good in that it shows that starting processes boils down to the system calls fork(), exec(), wait(), etc.
My shell has function calls, loops, conditionals, pipelines, subshells, command substitution, redirects, here docs, etc. (The code has some messiness, but the architecture is clean IMO.)
It turns out that these features require just a few more system calls -- dup2() and fcntl() to manipulate file descriptors, pipe(), and open() / read() / write() / close(). It's a good reminder of how simple Unix is. The complexity of the shell is basically all in string processing, and not in interfacing with the kernel (although the interactive parts of the shell do complicate things).
These system calls are all available in Python, so the code ends up being comparable to what you would write in C (and I'm in the process of porting to C++ now that the architecture has settled.)
[0] - http://xon.sh/
And bugs that would cause problems in the shell are unlikely to be of the unterminated string type, but more likely to be logic errors (redirect to the wrong file, mess up globbing, etc), and Python would not help you there.
In fact thinking that Python makes you safer is a very dangerous attitude. Someone programming with that mindset is likely to have less safe code than a C programmer who knows he has to do it right.
Of course there is still the possibility of logical errors.
Have a look here: http://www.cvedetails.com/product/21050/GNU-Bash.html?vendor...
One of the quick tests I like to do to ascertain the complexity of a codebase is "how long does it take to find the entrypoint" and "how long does it take to find the core functionality"?
In this case, I have been clicking around through nearly empty directories for 15+ minutes and haven't seen anything that looks like an entrypoint yet, nevermind the main loop.
In contrast, I downloaded the Bash source and within 5 minutes found the main loop (eval.c) and entrypoint (shell.c).
Now I'm curious to know what the cmd.exe source is like, but MS seems to have no intention of releasing that.
I'm not making any statement on the complexity of the general Powershell codebase, but finding the entrypoint at least seems straightforward.
- I had the exact same problem - "how do I get at the entrypoint and follow this" - only earlier today, with Chromium. I was trying to figure out why sync was broken and thought I'd try and follow the (C++) breadcrumbs. It didn't go very well. https://bugs.chromium.org/p/chromium/issues/detail?id=671498
- AFAIK, cmd.exe is basically a horrible, horrible hack. I'm not 100% sure, but I think an instance of cmd.exe is the only way you can run things with a stdout, as in Windows has no concept of TTYs - the cmd.exe process uses a bunch of undocumented kernel interface APIs to "make it work™". Related: https://github.com/Microsoft/BashOnWindows/issues/111#issuec...
I have to say though, the writeup on that Chromium ticket I filed was absolutely awesome. Did someone here notice...? :P
https://github.com/PowerShell/PowerShell/blob/master/src/pow...
It's instantiating the execution engine (.NET-speak for the core runtime) getting ready to run Monad (the original codename for PowerShell).
I think part of it is familiarity and context. I knew none of the command bits would be likely to contain an entrypoint. Directories that mentioned native looked useful for finding an entrypoint, because I know that PowerShell is implemented in C# - I reasoned I'd be able to find further managed entrypoints by looking at where it starts out in C++.
You can see that the main object it instantiates is Microsoft.PowerShell.UnmanagedPSEntry. Looks useful.
A search across the repo for UnmanagedPSEntry lead me to https://github.com/PowerShell/PowerShell/tree/master/src/Mic... which seems to contain all the entrypoints you're looking for.
The main loop is in InputLoop in https://github.com/PowerShell/PowerShell/blob/master/src/Mic...
(FTR, this took me about 8 minutes, including finding links that didn't include hashes.)
The shell is almost what distinguishes Unix from Windows, and that is apparent at the lowest levels.
The author probably started it as a learning excercise.
I mention that on the blog, but I haven't written about it a lot since I haven't implemented the language yet. It's designed with a big doc but not implemented yet.
Have you ever written a completion function in bash? IMO it's kind of a nightmare. That should be one of the initial use cases for a better language. It would be closer to writing it in Python or ES6 rather than bash.
If you just wanted to use sh syntax, then the reason you would use it is because it will have better parse errors and better runtime errors, which I talk about on my blog. But right now I don't actually expect anyone to use it, because it's in the early stages, like I say.
I suffer from compulsory C review disorder, so just a few quick points:
- The pattern "x = realloc(x, ...)" is a bad idea, it leaks the original memory on failure. Since the code seems to car about its memory management (and since it's a tutorial), I think this is worth mentioning (and fixing).
- I generally recommend against scaling string allocations by sizeof (char); that's always 1 so it doesn't do anything. Some people seem to feel that it's part of a general usage pattern that makes the intent more clear, though.
- I would recommend more "const" and "static", but some people seem to not care.
- I would use more size_t rather than int for things that are sizes. This is more clear, and also safer since it's unsigned.
- Using strtok() is not always the best choice, it has issues, but here it's basically doing what it was designed to do I guess.
What would the alternative be here? Allocate a new region, copy everything over and free the other region? Or is there something better?
> I generally recommend against scaling string allocations by sizeof (char); that's always 1 so it doesn't do anything. Some people seem to feel that it's part of a general usage pattern that makes the intent more clear, though.
Isn't this just a habit born out of portability concerns?
No.
If realloc fails it returns NULL. In which case the original `x` is still valid. ==> However with `x = realloc(x,...)` you don't don't have a reference to `x` any more!
y = realloc(x, ...);
About sizeof (char), there can be no "portability concerns", and that very thing is what I think gives rise to a lot of (in my opinion, bad) cargo cult programming. The value of "sizeof (char)" in C is 1. Note that I didn't say "using GCC x.y.z on x86". It's true for all conforming compilers, on all platforms, and on all architectures. It's defined by the language.
> The value of "sizeof (char)" in C is 1.
[1] http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf
y = realloc(x, ...)
if (y == null) {
free(x);
// Handle OOM situation
}
x = y;If you look at what the code does after that...
if (!buffer) {
fprintf(stderr, "lsh: allocation error\n");
exit(EXIT_FAILURE);
}
In general, I think the "this pattern is bad" sort of "thinking" is itself a bad idea; when writing and examining code, you should be looking at each situation itself and thinking to evaluate it, not just trying to match everything into one "pattern" or another. Does "x = realloc(x, ...)" make sense in all contexts? No. Does it make sense here? Yes. Otherwise it is a path towards mindless cargo-cultism, something which beginners should certainly be discouraged from doing.
I do really try to look at the situation, but that doesn't change the fact (at least in my experience) that there are patterns of "bad code" that seem to have a life of their own.
Probably caused by things being unintuitive, and/or more complex than people first realize, or something.
I'm really opposed to cargo cult programming, so no argument there. :)
Although I know many places use this project.
You don't need any library for that.
It's also from scratch (no libraries).
The professor provides an extensive test suite to check your implementation.
https://pdos.csail.mit.edu/6.828/2016/homework/xv6-shell.htm...
First published in 1985; for me ranks up there with K&R The C Programming Language and K&P The UNIX Programming Environment.
As far as I can tell, it's about using the kernel programming interface, which is of course very relevant to writing a shell. But I don't see anything about the shell specifically here:
As it suggests, he adds features to the shell as he introduces the system calls needed. You can see the source here
http://basepath.com/aup/ex/group__AUP2ex.html#Chap. 5
See files sh0.c (for versions 1 2 3) and sh3.c for version 4.
Which made the whole project boring to me, since it would've just come down to 3 well-defined, already solved problems: 1. write shell language grammar file 2.Use something like flex/bison (nowadays maybe antlr, or whatever) to generate the shell language parser 3. Implement the behaviour of the shell as reactions to parser events
At that wasn't interesting because: 1. I wanted to be POSIX compatible, the POSIX shell langauge is well defined, writing the grammar for that would've been boring 2. Boring by design, the whole point of using parser generators is making compiler/interpreter writing an easy, boring task 3. Arguably, this would've been interesting, to see how to do it. But if you already have a deep understandidg how a *nix shell does what it does, not that interesting anymore...
But that's not what's happening in the article -- he is showing a simple REPL and fork() exec(), which is about as much as you can expect to do in an article that long. lsh_split_line() in no way resembles a real shell lexer, and there is no parser, since there are no programming language features like function calls, loops, and conditionals. Not to mention pipelines, subshells, and redirects.
I think you're overestimating the power of flex, bison, and ANTLR. I actually ported the POSIX shell grammar to ANTLR -- it's not usable as the basis for a shell parser. The POSIX grammar also only covers 1 of 4 sublanguages in shell, and it's a significantly smaller language than bash.
Bash uses bison/yacc, and maintainer Chet Ramey talks about how it was a mistake here:
http://www.aosabook.org/en/bash.html
My blog is basically about parsing bash, and I discovered a lot of interesting things:
http://www.oilshell.org/blog/2016/10/20.html
I guess, I might've been too optimistic about the power of parser generators. Still, I think if someone were to start implementing a shell, I'd advise them to start with the grammer/lexer/parser part, either implementing them themselves or trying some of the generators. I think it's the right way to go about it (just wasn't what I thought I'd be doing when implementing a shell, at the time)
I did do a few things with parser generators though. Granted, nothing (yet) as complex as bash or even just POSIX, but still, they each had their own little trickinesses. E.g.:
https://github.com/BugsBunnySan/edl (ANTLR4 / Python)
https://github.com/BugsBunnySan/Phat-Agnus (YAPP / Perl)
I mostly write Python and if you are looking for a shell written in Python, check xon.sh [0]
[0] - http://xon.sh
I'll just leave this here.
http://unix.derkeiler.com/Newsgroups/comp.unix.shell/2009-10...
Like shells? This is the link you didn't know you were looking for, but were hoping to find anyway.
Adding some of these requirements as an afterthought into a command interpreter will likely be a pain in the butt. Ctrl-C is usually done with a longjmp(). Unplanned introductions of setjmp/longjmp into a code base could wind up with leaks or stability issues. (Side note: don't write a shell in C: pick some open source managed language in which it is safe to throw an exception out of a signal handler.)
Another requirement is arranging pipes, and handling out-of-order termination of the pipeline elements; a shell must juggle multiple child processes in order to support pipes. Pipes are put into process groups called jobs, etc.
Without all these features, you don't have a Unix shell; just an interpreter for a simple command language.
That said, I don't really see why Ctrl-C has anything to do with `longjmp` - and I say that having written a shell capable of doing the above. When talking about TTY functionality, the OS (or whatever handles the TTY layer) handles the Ctrl- keys. All the shell has to do in that instance is use `waitpid` (or similar) to wait for a process to die/suspend/etc. and then handle deciding what to (Such as changing the foreground process). When you press Ctrl-C while running a process, the shell never receives a SIGINT, only the current foreground process.
I guess I need to do a test of doing some expensive computation in bash, and then hitting Ctrl-C. Like doing the mandelbrot set or something.
bash$ while true ; do : ; done
^C
bash$I think you can use any of C++ exceptions, explicit returns, or setlongjmp(). setlongjmp() doesn't work well with C++ destructors. The interpreter loop just has to check for a flag set by the signal handler and then pop back to the interactive loop.
I noticed that the Lua parser uses setlongjmp() when compiled as C, but C++ exceptions when compiled as C++.
[1] https://github.com/dspinellis/unix-history-repo/tree/Bell-Re...
[2] https://github.com/dspinellis/unix-history-repo/tree/BSD-2-S...
That said, a shell's remarkably limited scope is actually something C is reasonably suited for.
Garbage collection almost always interacts poorly with signal handling. You can't interrupt a garbage collector at an arbitrary point.
I wanted to bootstrap my shell [1] with Lisp -- and I hacked on femtolisp because Julia is bootstrapped in exactly this manner. And for awhile I thought about using an OCaml front end.
But in the end I settled on C++ (writing 3K lines of code, which I plan to return to after my prototype is done.) C++ lets you do fork(), exec() and handle signals exactly as in C, but it actually has useful string abstractions!
C++ has a lot of problems, but it appears to be the best tool for this job.
As far as signal handling goes, it's in the box. See this Rosetta Code example under the task "Find limits of recursion" where we catch a SIGSEGV using a TXR Lisp lambda (running on an alternate stack via sigaltstack):
https://rosettacode.org/wiki/Find_limit_of_recursion#TXR
Handling a SIGINT:
https://rosettacode.org/wiki/Handle_a_signal#TXR
Programming reference:
http://www.nongnu.org/txr/txr-manpage.html#N-010CFD89
You don't have to worry about signal handlers and garbage collection.
If you need to do something in C++, the TXR code base will support you. Though it is C, it all compiles in C++, which I check for regressions every release. (At this time, I won't accept patches which break away from C compatibility and cause C++ to be required, but for experimenting and forking off your own thing, there it is.) Just ./configure cc=g++ and off you go.
TXR also integrates a nicely hacked version of Linenoise that could be used to bootstrap the shell command prompt. I rewrote the multi-line support so that it is excellent. There is visual cut/copy/paste, paren matching, undo, and more. (It's the only part of TXR without proper Unicode support, unfortunately: in the TODO list.)
Instead, it looks like I will generate a lot of C++ from Python to control the complexity (and line count).
For example, right now I'm working with Zephyr ASDL, which is basically a DSL for algebraic data types which can bridge Python and C++. You can do this in Lisps too of course, but Python works just as well in this case. Julia is interesting because the lexer and parser are in femtolisp, and that enables Julia macros.
If I'm reading your page right, Python handles signals the same way -- it receives the signal in C, and then runs a Python handler later on the main interpreter loop. I think you pretty much have to do it that way.
(But Python has some logic about turning certain signals into exceptions on the main thread, which I don't want to bother with.)
I wrote on some related topics here:
There is a flag which enables or disables async signals. In the case of a CPU exception signal (SEGV, BUS, ILL, FPE, ...), we ignore this flag and just do async. Other signals respect the async flag. The async flag is almost always off; async signals are enabled in various places in the library when blocking system calls are being made. So for instance an async signal won't go off during garbage collection; the internal handler will see that async signaling is disabled, and arrange for a deferred call at the next opportunity (unless it is a CPU exception).
Will be a great base to start with and should be a great learning experience trying to make it more functional.
sweet, sweet nightmares of yonder.