| Message ID | 20210701061611.957918-1-seanga2@gmail.com |
|---|---|
| Headers | show |
| Series | cli: Add a new shell | expand |
On Thu, Jul 01, 2021 at 02:15:43AM -0400, Sean Anderson wrote: > Well, this has been sitting on my hard drive for too long without feedback > ("Release early, release often"), so here's the first RFC. This is not ready to > merge (see the "Future work" section below), but the shell is functional and at > least partially tested. > > The goal is to have 0 bytes gained over Hush. Currently we are around 800 bytes > over on sandbox. A good goal, but perhaps slightly too strict? > > add/remove: 90/54 grow/shrink: 3/7 up/down: 12834/-12042 (792) > > = Getting started > > Enable CONFIG_LIL. If you would like to run tests, enable CONFIG_LIL_FULL. Note > that dm_test_acpi_cmd_dump and setexpr_test_str_oper will fail. CONFIG_LIL_POOLS > is currently broken (with what appears to be a double free). > > For an overview of the language as a whole, refer to the original readme [1]. > > [1] http://runtimeterror.com/tech/lil/readme.txt > > == Key patches > > The following patches are particularly significant for reviewing and > understanding this series: > > cli: Add LIL shell > This contains the LIL shell as originally written by Kostas with some > major deletions and some minor additions. > cli: lil: Wire up LIL to the rest of U-Boot > This allows you to use LIL as a shell just like Hush. > cli: lil: Document structures > This adds documentation for the major structures of LIL. It is a good > place to start looking at the internals. > test: Add tests for LIL > This adds some basic integration tests and provides some examples of > LIL code. > cli: lil: Add a distinct parsing step > This adds a parser separate from the interpreter. This patch is the > largest original work in this series. > cli: lil: Load procs from the environment > This allows procedures to be saved and loaded like variables. > > = A new shell > > This series adds a new shell for U-Boot. The aim is to eventually replace Hush > as the primary shell for all boards which currently use it. Hush should be > replaced because it has several major problems: > > - It has not had a major update in two decades, resulting in duplication of > effort in finding bugs. Regarding a bug in variable setting, Wolfgang remarks > > So the specific problem has (long) been fixed in upstream, and > instead of adding a patch to our old version, thus cementing the > broken behaviour, we should upgrade hush to recent upstream code. > > -- Wolfgang Denk [2] > > These lack of updates are further compounded by a significant amount of > ifdef-ing in the Hush code. This makes the shell hard to read and debug. > Further, the original purpose of such ifdef-ing (upgrading to a newer Hush) > has never happened. > > - It was designed for a preempting OS which supports pipes and processes. This > fundamentally does not match the computing model of U-Boot where there is > exactly one thread (and every other CPU is spinning or sleeping). Working > around these design differences is a significant cause of the aformentioned > ifdef-ing. > > - It lacks many major features expected of even the most basic shells, such > as functions and command substitution ($() syntax). This makes it difficult > to script with Hush. While it is desirable to write some code in C, much code > *must* be written in C because there is no way to express the logic in Hush. > > I believe that U-Boot should have a shell which is more featureful, has cleaner > code, and which is the same size as Hush (or less). The ergonomic advantages > afforded by a new shell will make U-Boot easier to use and customize. > > [2] https://lore.kernel.org/u-boot/872080.1614764732@gemini.denx.de/ First, great! Thanks for doing this. A new shell really is the only viable path forward here, and I appreciate you taking the time to evaluate several and implement one. > = Open questions > > While the primary purpose of this series is of course to get feedback on the > code I have already written, there are several decisions where I am not sure > what the best course of action is. > > - What should be done about 'expr'? The 'expr' command is a significant portion > of the final code size. It cannot be removed outright, because it is used by > several builtin functions like 'if', 'while', 'for', etc. The way I see it, > there are two general approaches to take > > - Rewrite expr to parse expressions and then evaluate them. The parsing could > re-use several of the existing parse functions like how parse_list does. > This could reduce code, as instead of many functions each with their own > while/switch statements, we could have two while/switch statements (one to > parse, and one to evaluate). However, this may end up increasing code size > (such as when the main language had evaluation split from parsing). > > - Don't parse infix expressions, and just make arithmetic operators normal > functions. This would affect ergonomics a bit. For example, instead of > > if {$i < 10} { ... } > > one would need to write > > if {< $i 10} { ... } > > and instead of > > if {$some_bool} { ... } > > one would need to write > > if {quote $some_bool} { ... } > > Though, given how much setexpr is used (not much), this may not be such a > big price to pay. This route is almost certain to reduce code size. So, this is a question because we have cmd/setexpr.c that provides "expr" today? Or because this is a likely place to reclaim some of that 800 byte growth? > - How should LIL functions integrate with the rest of U-Boot? At the moment, lil > functions and procedures exist in a completely separate world from normal > commands. I would like to integrate them more closely, but I am not sure the > best way to go about this. At the very minimum, each LIL builtin function > needs to get its hands on the LIL interpreter somehow. I'd rather this didn't > happen through gd_t or similar so that it is easier to unit test. > Additionally, LIL functions expect an array of lil_values instead of strings. > We could strip them out, but I worry that might start to impact performance > (from all the copying). I might be missing something here. But, given that whenever we have C code run-around and generate a string to then pass to the interpreter to run, someone asks why we don't just make API calls directly, perhaps the answer is that we don't need to? > > The other half of this is adding LIL features into regular commands. The most > important feature here is being able to return a string result. I took an > initial crack at it [3], but I think with this series there is a stronger > motivating factor (along with things like [4]). > > [3] https://patchwork.ozlabs.org/project/uboot/list/?series=231377 > [4] https://patchwork.ozlabs.org/project/uboot/list/?series=251013 > > = Future work > > The series as presented today is incomplete. The following are the major issues > I see with it at the moment. I would like to address all of these issues, but > some of them might be postponed until after first merging this series. > > - There is a serious error handling problem. Most original LIL code never > checked errors. In almost every case, errors were silently ignored, even > malloc failures! While I have designed new code to handle errors properly, > there still remains a significant amount of original code which just ignores > errors. In particular, I would like to ensure that the following categories of > error conditions are handled: > > - Running out of memory. > - Access to a nonexistant variable. > - Passing the wrong number of arguments to a function. > - Interpreting a value as the wrong type (e.g. "foo" should not have a numeric > representation, instead of just being treated as 1). > > - There are many deviations from TCL with no purpose. For example, the list > indexing function is named "index" and not "lindex". It is perfectly fine to > drop features or change semantics to reduce code size, make parsing easier, > or make execution easier. But changing things for the sake of it should be > avoided. > > - The test suite is rather anemic compared with the amount of code this > series introduces. I would like to expand it significantly. In particular, > error conditions are not well tested (only the "happy path" is tested). > > - While I have documented all new functions I have written, there are many > existing functions which remain to be documented. In addition, there is no > user documentation, which is critical in driving adoption of any new > programming language. Some of this cover letter might be integrated with any > documentation written. > > - Some shell features such as command repetition and secondary shell prompts > have not been implemented. > > - Arguments to native lil functions are incompatible with U-Boot functions. For > example, the command > > foo bar baz > > would be passed to a U-Boot command as > > { "foo", "bar", "baz", NULL } > > but would be passed to a LIL function as > > { "bar", "baz" } > > This makes it more difficult to use the same function to parse several > different commands. At the moment this is solved by passing the command name > in lil->env->proc, but I would like to switch to the U-Boot argument list > style. > > - Several existing tests break when using LIL because they expect no output on > failure, but LIL produces some output notifying the user of the failure. > > - Implement DISTRO_BOOT in LIL. I think this is an important proof-of-concept to > show what can be done with LIL, and to determine which features should be > moved to LIL_FULL. > > = Why Lil? > > When looking for a suitable replacement shell, I evaluated implementations using > the following criteria: > > - It must have a GPLv2-compatible license. > - It must be written in C, and have no major external dependencies. > - It must support bare function calls. That is, a script such as 'foo bar' > should invoke the function 'foo' with the argument 'bar'. This preserves the > shell-like syntax we expect. > - It must be small. The eventual target is that it compiles to around 10KiB with > -Os and -ffunction-sections. > - There should be good tests. Any tests at all are good, but a functioning suite > is better. > - There should be good documentation > - There should be comments in the source. > - It should be "finished" or have only slow development. This will hopefully > make it easier to port changes. On this last point, I believe this is based on lil20190821 and current is now lil20210502. With a quick diff between them, I can see that the changes there are small enough that while you've introduced a number of changes here, it would be a very easy update. > Notably absent from the above list is performance. Most scripts in U-Boot will > be run once on boot. As long as the time spent evaluating scripts is kept under > a reasonable threshold (a fraction of the time spend initializing hardware or > reading data from persistant storage), there is no need to optimize for speed. > > In addition, I did not consider updating Hush from Busybox. The mismatch in > computing environment expectations (as noted in the "New shell" section above) > still applies. IMO, this mismatch is the biggest reason that things like > functions and command substitution have been excluded from the U-Boot's Hush. > > == lil > > - zLib > - TCL > - Compiles to around 10k with no builtins. To 25k with builtins. > - Some tests, but not organized into a suite with expected output. Some evidence > that the author ran APL, but no harness. > - Some architectural documentation. Some for each functions, but not much. > - No comments :l > - 3.5k LoC > > == picol > > - 2-clause BSD > - TCL > - Compiles to around 25k with no builtins. To 80k with builtins. > - Tests with suite (in-language). No evidence of fuzzing. > - No documentation :l > - No comments :l > - 5k LoC > > == jimtcl > > - 2-clause BSD > - TCL > - Compiles to around 95k with no builtins. To 140k with builtins. Too big... > > == boron > > - LGPLv3+ (so this is right out) > - REBOL > - Compiles to around 125k with no builtins. To 190k with builtins. Too big... > > == libmawk > > - GPLv2 > - Awk > - Compiles to around 225k. Too big... > > == libfawk > > - 3-clause BSD > - Uses bison+yacc... > - Awk; As it turns out, this has parentheses for function calls. > - Compiles to around 24-30k. Not sure how to remove builtins. > - Test suite (in-language). No fuzzing. > - Tutorial book. No function reference. > - No comments > - Around 2-4k LoC > > == MicroPython > > - MIT > - Python (but included for completeness) > - Compiles to around 300k. Too big... > > == mruby/c > > - 3-clause BSD > - Ruby > - Compiles to around 85k without builtins and 120k with. Too big... > > == eLua > > - MIT > - Lua > - Build system is a royal pain (custom and written in Lua with external deps) > - Base binary is around 250KiB and I don't want to deal with reducing it > > So the interesting/viable ones are > - lil > - picol > - libfawk (maybe) > > I started with LIL because it was the smallest. I have found several > issues with LIL along the way. Some of these are addressed in this series > already, while others remain unaddressed (see the section "Future Work"). Thanks for the evaluations, of these, lil does make the most sense.
Dear Tom, In message <20210701202155.GQ9516@bill-the-cat> you wrote: > > First, great! Thanks for doing this. A new shell really is the only > viable path forward here, and I appreciate you taking the time to > evaluate several and implement one. I disagree that a new shell is the _only_ way forward. AFAICT, all the raised concerns have long been fixed in upstream versions of hush; see for example [1]: ... //config: hush is a small shell. It handles the normal flow control //config: constructs such as if/then/elif/else/fi, for/in/do/done, while loops, //config: case/esac. Redirections, here documents, $((arithmetic)) //config: and functions are supported. //config: [1] https://git.busybox.net/busybox/tree/shell/hush.c#n98 My gut feeling is that updating to a recent version of hush is the most efficent _backward_compatible_ way. And if we drop that requirement, we might even take a bigger step and move to lua - which would allow for a complete new level of script based extensions. > > - There is a serious error handling problem. Most original LIL code never > > checked errors. In almost every case, errors were silently ignored, even > > malloc failures! While I have designed new code to handle errors properly, > > there still remains a significant amount of original code which just ignores > > errors. In particular, I would like to ensure that the following categories of > > error conditions are handled: This is something that scares me like hell. This in a shell? For me this is close to a killing point. > > - Running out of memory. > > - Access to a nonexistant variable. > > - Passing the wrong number of arguments to a function. > > - Interpreting a value as the wrong type (e.g. "foo" should not have a numeric > > representation, instead of just being treated as 1). Who says so? Bash says: -> printf "%d\n" foo -bash: printf: foo: invalid number 0 So it is _not_ 1 ... > > - There are many deviations from TCL with no purpose. For example, the list > > indexing function is named "index" and not "lindex". It is perfectly fine to > > drop features or change semantics to reduce code size, make parsing easier, > > or make execution easier. But changing things for the sake of it should be > > avoided. It's not a standard POSIX shell, it's not TCL (ick!), ... it's something new, incompatible... > Thanks for the evaluations, of these, lil does make the most sense. You mean, adding a complete new, incompatible and non-standard shell is a better approach than updating to a recent version of hush? What makes you think so? Best regards, Wolfgang Denk
On 7/2/21 7:30 AM, Wolfgang Denk wrote: > Dear Tom, > > In message <20210701202155.GQ9516@bill-the-cat> you wrote: >> >> First, great! Thanks for doing this. A new shell really is the only >> viable path forward here, and I appreciate you taking the time to >> evaluate several and implement one. > > I disagree that a new shell is the _only_ way forward. > > AFAICT, all the raised concerns have long been fixed in upstream > versions of hush; see for example [1]: > > ... > //config: hush is a small shell. It handles the normal flow control > //config: constructs such as if/then/elif/else/fi, for/in/do/done, while loops, > //config: case/esac. Redirections, here documents, $((arithmetic)) > //config: and functions are supported. > //config: > > [1] https://git.busybox.net/busybox/tree/shell/hush.c#n98 In fact, the code for most of this is present but ifdef'd out. The real issue is that the implementation of much of the above relies on things like fork() which we can't provide. > My gut feeling is that updating to a recent version of hush is the > most efficent _backward_compatible_ way. > > And if we drop that requirement, we might even take a bigger step > and move to lua - which would allow for a complete new level of > script based extensions. I'm not aware of any Lua implementations which meet the size requirements for U-Boot. Any port would need to be either written from scratch or have some serious modification, not unlike what I've done here. >>> - There is a serious error handling problem. Most original LIL code never >>> checked errors. In almost every case, errors were silently ignored, even >>> malloc failures! While I have designed new code to handle errors properly, >>> there still remains a significant amount of original code which just ignores >>> errors. In particular, I would like to ensure that the following categories of >>> error conditions are handled: > > This is something that scares me like hell. This in a shell? For > me this is close to a killing point. Yes, it was for me as well. But it is not something so obvious unless you are looking for it. I believe I have addressed this issue in much of the core code (parser and interpreter). But the builtin commands must be gone through and converted. >>> - Running out of memory. >>> - Access to a nonexistant variable. >>> - Passing the wrong number of arguments to a function. >>> - Interpreting a value as the wrong type (e.g. "foo" should not have a numeric >>> representation, instead of just being treated as 1). > > Who says so? The current LIL code. > > Bash says: > > -> printf "%d\n" foo > -bash: printf: foo: invalid number > 0 > > So it is _not_ 1 ... And I would like to replicate this behavior. > >>> - There are many deviations from TCL with no purpose. For example, the list >>> indexing function is named "index" and not "lindex". It is perfectly fine to >>> drop features or change semantics to reduce code size, make parsing easier, >>> or make execution easier. But changing things for the sake of it should be >>> avoided. > > It's not a standard POSIX shell, it's not TCL (ick!), ... it's > something new, incompatible... And Hush isn't POSIX either :) But as noted above, I would like to hew much closer to TCL than LIL has traditionally done. >> Thanks for the evaluations, of these, lil does make the most sense. > > You mean, adding a complete new, incompatible and non-standard shell > is a better approach than updating to a recent version of hush? Correct. > What makes you think so? Hush relies heavily on its posix environment. Porting it has, and will, require substantial modification. IMO the work necessary will be around the same or more for Hush as for any other language. --Sean
On 7/1/21 4:21 PM, Tom Rini wrote: > On Thu, Jul 01, 2021 at 02:15:43AM -0400, Sean Anderson wrote: > >> Well, this has been sitting on my hard drive for too long without feedback >> ("Release early, release often"), so here's the first RFC. This is not ready to >> merge (see the "Future work" section below), but the shell is functional and at >> least partially tested. >> >> The goal is to have 0 bytes gained over Hush. Currently we are around 800 bytes >> over on sandbox. > > A good goal, but perhaps slightly too strict? Perhaps. But I think getting in the ballpark will significantly help drive adoption. I want to make it as easy as possible for maintainers to enable LIL and start using it. > >> >> add/remove: 90/54 grow/shrink: 3/7 up/down: 12834/-12042 (792) >> >> = Getting started >> >> Enable CONFIG_LIL. If you would like to run tests, enable CONFIG_LIL_FULL. Note >> that dm_test_acpi_cmd_dump and setexpr_test_str_oper will fail. CONFIG_LIL_POOLS >> is currently broken (with what appears to be a double free). >> >> For an overview of the language as a whole, refer to the original readme [1]. >> >> [1] http://runtimeterror.com/tech/lil/readme.txt >> >> == Key patches >> >> The following patches are particularly significant for reviewing and >> understanding this series: >> >> cli: Add LIL shell >> This contains the LIL shell as originally written by Kostas with some >> major deletions and some minor additions. >> cli: lil: Wire up LIL to the rest of U-Boot >> This allows you to use LIL as a shell just like Hush. >> cli: lil: Document structures >> This adds documentation for the major structures of LIL. It is a good >> place to start looking at the internals. >> test: Add tests for LIL >> This adds some basic integration tests and provides some examples of >> LIL code. >> cli: lil: Add a distinct parsing step >> This adds a parser separate from the interpreter. This patch is the >> largest original work in this series. >> cli: lil: Load procs from the environment >> This allows procedures to be saved and loaded like variables. >> >> = A new shell >> >> This series adds a new shell for U-Boot. The aim is to eventually replace Hush >> as the primary shell for all boards which currently use it. Hush should be >> replaced because it has several major problems: >> >> - It has not had a major update in two decades, resulting in duplication of >> effort in finding bugs. Regarding a bug in variable setting, Wolfgang remarks >> >> So the specific problem has (long) been fixed in upstream, and >> instead of adding a patch to our old version, thus cementing the >> broken behaviour, we should upgrade hush to recent upstream code. >> >> -- Wolfgang Denk [2] >> >> These lack of updates are further compounded by a significant amount of >> ifdef-ing in the Hush code. This makes the shell hard to read and debug. >> Further, the original purpose of such ifdef-ing (upgrading to a newer Hush) >> has never happened. >> >> - It was designed for a preempting OS which supports pipes and processes. This >> fundamentally does not match the computing model of U-Boot where there is >> exactly one thread (and every other CPU is spinning or sleeping). Working >> around these design differences is a significant cause of the aformentioned >> ifdef-ing. >> >> - It lacks many major features expected of even the most basic shells, such >> as functions and command substitution ($() syntax). This makes it difficult >> to script with Hush. While it is desirable to write some code in C, much code >> *must* be written in C because there is no way to express the logic in Hush. >> >> I believe that U-Boot should have a shell which is more featureful, has cleaner >> code, and which is the same size as Hush (or less). The ergonomic advantages >> afforded by a new shell will make U-Boot easier to use and customize. >> >> [2] https://lore.kernel.org/u-boot/872080.1614764732@gemini.denx.de/ > > First, great! Thanks for doing this. A new shell really is the only > viable path forward here, and I appreciate you taking the time to > evaluate several and implement one. > >> = Open questions >> >> While the primary purpose of this series is of course to get feedback on the >> code I have already written, there are several decisions where I am not sure >> what the best course of action is. >> >> - What should be done about 'expr'? The 'expr' command is a significant portion >> of the final code size. It cannot be removed outright, because it is used by >> several builtin functions like 'if', 'while', 'for', etc. The way I see it, >> there are two general approaches to take >> >> - Rewrite expr to parse expressions and then evaluate them. The parsing could >> re-use several of the existing parse functions like how parse_list does. >> This could reduce code, as instead of many functions each with their own >> while/switch statements, we could have two while/switch statements (one to >> parse, and one to evaluate). However, this may end up increasing code size >> (such as when the main language had evaluation split from parsing). >> >> - Don't parse infix expressions, and just make arithmetic operators normal >> functions. This would affect ergonomics a bit. For example, instead of >> >> if {$i < 10} { ... } >> >> one would need to write >> >> if {< $i 10} { ... } >> >> and instead of >> >> if {$some_bool} { ... } >> >> one would need to write >> >> if {quote $some_bool} { ... } >> >> Though, given how much setexpr is used (not much), this may not be such a >> big price to pay. This route is almost certain to reduce code size. > > So, this is a question because we have cmd/setexpr.c that provides > "expr" today? Or because this is a likely place to reclaim some of that > 800 byte growth? The latter. setexpr cannot be used because it does not return a result, and instead sets a (global) variable. The expression parsing functionality is core to LIL and used in many builtin commands (such as `if` above), and really needs to return a lil_value. > >> - How should LIL functions integrate with the rest of U-Boot? At the moment, lil >> functions and procedures exist in a completely separate world from normal >> commands. I would like to integrate them more closely, but I am not sure the >> best way to go about this. At the very minimum, each LIL builtin function >> needs to get its hands on the LIL interpreter somehow. I'd rather this didn't >> happen through gd_t or similar so that it is easier to unit test. >> Additionally, LIL functions expect an array of lil_values instead of strings. >> We could strip them out, but I worry that might start to impact performance >> (from all the copying). > > I might be missing something here. But, given that whenever we have C > code run-around and generate a string to then pass to the interpreter to > run, someone asks why we don't just make API calls directly, perhaps the > answer is that we don't need to? err, the issue here is that the signature for regular commands is rougly int cmd(..., int argc, char **argv, ...) and the signature for LIL commands is struct lil_value *cmd(struct lil *lil, size_t argc, struct lil_value **argv) where lil_value is struct lil_value { size_t l; char *d; }; so while regular commands can be reimplemented as LIL commands (just create a new argv containing the strings directly), it is more difficult to go the other way. I bring this up because I think having two separate ways to write a command is not the best way to do things going forward. >> >> The other half of this is adding LIL features into regular commands. The most >> important feature here is being able to return a string result. I took an >> initial crack at it [3], but I think with this series there is a stronger >> motivating factor (along with things like [4]). >> >> [3] https://patchwork.ozlabs.org/project/uboot/list/?series=231377 >> [4] https://patchwork.ozlabs.org/project/uboot/list/?series=251013 >> >> = Future work >> >> The series as presented today is incomplete. The following are the major issues >> I see with it at the moment. I would like to address all of these issues, but >> some of them might be postponed until after first merging this series. >> >> - There is a serious error handling problem. Most original LIL code never >> checked errors. In almost every case, errors were silently ignored, even >> malloc failures! While I have designed new code to handle errors properly, >> there still remains a significant amount of original code which just ignores >> errors. In particular, I would like to ensure that the following categories of >> error conditions are handled: >> >> - Running out of memory. >> - Access to a nonexistant variable. >> - Passing the wrong number of arguments to a function. >> - Interpreting a value as the wrong type (e.g. "foo" should not have a numeric >> representation, instead of just being treated as 1). >> >> - There are many deviations from TCL with no purpose. For example, the list >> indexing function is named "index" and not "lindex". It is perfectly fine to >> drop features or change semantics to reduce code size, make parsing easier, >> or make execution easier. But changing things for the sake of it should be >> avoided. >> >> - The test suite is rather anemic compared with the amount of code this >> series introduces. I would like to expand it significantly. In particular, >> error conditions are not well tested (only the "happy path" is tested). >> >> - While I have documented all new functions I have written, there are many >> existing functions which remain to be documented. In addition, there is no >> user documentation, which is critical in driving adoption of any new >> programming language. Some of this cover letter might be integrated with any >> documentation written. >> >> - Some shell features such as command repetition and secondary shell prompts >> have not been implemented. >> >> - Arguments to native lil functions are incompatible with U-Boot functions. For >> example, the command >> >> foo bar baz >> >> would be passed to a U-Boot command as >> >> { "foo", "bar", "baz", NULL } >> >> but would be passed to a LIL function as >> >> { "bar", "baz" } >> >> This makes it more difficult to use the same function to parse several >> different commands. At the moment this is solved by passing the command name >> in lil->env->proc, but I would like to switch to the U-Boot argument list >> style. >> >> - Several existing tests break when using LIL because they expect no output on >> failure, but LIL produces some output notifying the user of the failure. >> >> - Implement DISTRO_BOOT in LIL. I think this is an important proof-of-concept to >> show what can be done with LIL, and to determine which features should be >> moved to LIL_FULL. >> >> = Why Lil? >> >> When looking for a suitable replacement shell, I evaluated implementations using >> the following criteria: >> >> - It must have a GPLv2-compatible license. >> - It must be written in C, and have no major external dependencies. >> - It must support bare function calls. That is, a script such as 'foo bar' >> should invoke the function 'foo' with the argument 'bar'. This preserves the >> shell-like syntax we expect. >> - It must be small. The eventual target is that it compiles to around 10KiB with >> -Os and -ffunction-sections. >> - There should be good tests. Any tests at all are good, but a functioning suite >> is better. >> - There should be good documentation >> - There should be comments in the source. >> - It should be "finished" or have only slow development. This will hopefully >> make it easier to port changes. > > On this last point, I believe this is based on lil20190821 and current > is now lil20210502. With a quick diff between them, I can see that the > changes there are small enough that while you've introduced a number of > changes here, it would be a very easy update. From what I understand, the only changes are updated copyrights and the addition of a license file to cover the tests. --Sean
Hello Sean, On 01.07.21 08:15, Sean Anderson wrote: > Well, this has been sitting on my hard drive for too long without feedback > ("Release early, release often"), so here's the first RFC. This is not ready to > merge (see the "Future work" section below), but the shell is functional and at > least partially tested. > > The goal is to have 0 bytes gained over Hush. Currently we are around 800 bytes > over on sandbox. > > add/remove: 90/54 grow/shrink: 3/7 up/down: 12834/-12042 (792) Thanks for this comparison. Here just my thoughts, but I have currently to low time to follow here completly, so sorry if I miss stuff already discussed. From my side of view we can add a second shell beside hush, and as you already mentioned it may is even possible to start LIL from hush. This would be cool. But I disagree in the following points: - I do not see why LIL should *replace* hush. This may break a lot of current boards. Also I see no need to do this, as if you do complex stuff in u-boot shell it may is the wrong way and you have to think about... and I see no big discussions here about BUGS in our current hush implementation ... may it makes sense to bring them up and fix? - Is LIL really so good code, that it is done? Or is there only no community which develop further? - Do we really want code, which does no error checking? Commentless code... you wrote: > - There is a serious error handling problem. Most original LIL code never > checked errors. In almost every case, errors were silently ignored, even > malloc failures! While I have designed new code to handle errors properly, Which really let me think, nobody is interested in this code ... this sounds like crap... and this brings me to the next point - Do we not have the same problem as with hush, if we change LIL code? Do you plan to upstream your changes? So please do not understand me wrong, I see you invested much time here, but I see LIL not in the short term as a replacement for hush. I would accept to add LIL as an option and we will see, how good it works. And if we have in lets say 2-3 years more boards which use LIL instead of hush *and* also active maintained LIL code, we may can think of getting rid of hush... and may have a "hush compatibility" layer... I have no idea of current hush mainline code and how many work it will be to update U-Boot to a current hush version. But may this would be make more sense as hush is in active development. Also may to discuss with hush maintainers to upstream U-Boot changes... this would make in my eyes more sense. > = Why Lil? > > When looking for a suitable replacement shell, I evaluated implementations using > the following criteria: > > - It must have a GPLv2-compatible license. > - It must be written in C, and have no major external dependencies. > - It must support bare function calls. That is, a script such as 'foo bar' > should invoke the function 'foo' with the argument 'bar'. This preserves the > shell-like syntax we expect. > - It must be small. The eventual target is that it compiles to around 10KiB with > -Os and -ffunction-sections. > - There should be good tests. Any tests at all are good, but a functioning suite > is better. > - There should be good documentation > - There should be comments in the source. > - It should be "finished" or have only slow development. This will hopefully > make it easier to port changes. > > Notably absent from the above list is performance. Most scripts in U-Boot will > be run once on boot. As long as the time spent evaluating scripts is kept under > a reasonable threshold (a fraction of the time spend initializing hardware or > reading data from persistant storage), there is no need to optimize for speed. > > In addition, I did not consider updating Hush from Busybox. The mismatch in > computing environment expectations (as noted in the "New shell" section above) > still applies. IMO, this mismatch is the biggest reason that things like > functions and command substitution have been excluded from the U-Boot's Hush. > > == lil > > - zLib > - TCL > - Compiles to around 10k with no builtins. To 25k with builtins. > - Some tests, but not organized into a suite with expected output. Some evidence > that the author ran APL, but no harness. > - Some architectural documentation. Some for each functions, but not much. > - No comments :l > - 3.5k LoC > > == picol > > - 2-clause BSD > - TCL > - Compiles to around 25k with no builtins. To 80k with builtins. > - Tests with suite (in-language). No evidence of fuzzing. > - No documentation :l > - No comments :l > - 5k LoC > > == jimtcl > > - 2-clause BSD > - TCL > - Compiles to around 95k with no builtins. To 140k with builtins. Too big... > > == boron > > - LGPLv3+ (so this is right out) > - REBOL > - Compiles to around 125k with no builtins. To 190k with builtins. Too big... > > == libmawk > > - GPLv2 > - Awk > - Compiles to around 225k. Too big... > > == libfawk > > - 3-clause BSD > - Uses bison+yacc... > - Awk; As it turns out, this has parentheses for function calls. > - Compiles to around 24-30k. Not sure how to remove builtins. > - Test suite (in-language). No fuzzing. > - Tutorial book. No function reference. > - No comments > - Around 2-4k LoC > > == MicroPython > > - MIT > - Python (but included for completeness) > - Compiles to around 300k. Too big... > > == mruby/c > > - 3-clause BSD > - Ruby > - Compiles to around 85k without builtins and 120k with. Too big... > > == eLua > > - MIT > - Lua > - Build system is a royal pain (custom and written in Lua with external deps) > - Base binary is around 250KiB and I don't want to deal with reducing it > > So the interesting/viable ones are > - lil > - picol > - libfawk (maybe) Very nice overview, thanks! bye, Heiko
On 7/7/21 11:49 PM, Heiko Schocher wrote: > Hello Sean, > > On 01.07.21 08:15, Sean Anderson wrote: >> Well, this has been sitting on my hard drive for too long without feedback >> ("Release early, release often"), so here's the first RFC. This is not ready to >> merge (see the "Future work" section below), but the shell is functional and at >> least partially tested. >> >> The goal is to have 0 bytes gained over Hush. Currently we are around 800 bytes >> over on sandbox. >> >> add/remove: 90/54 grow/shrink: 3/7 up/down: 12834/-12042 (792) > > Thanks for this comparison. Here just my thoughts, but I have currently to > low time to follow here completly, so sorry if I miss stuff already > discussed. > > From my side of view we can add a second shell beside hush, and as you > already mentioned it may is even possible to start LIL from hush. This > would be cool. > > But I disagree in the following points: > > - I do not see why LIL should *replace* hush. This is the eventual goal. This series just adds an option at build time (CONFIG_LIL) which uses LIL as the shell instead of Hush. But anyone who writes a series like this must be convinced that it is better than what already exists. So I write that my goal is to replace hush, even if I think that it will take a long while. > This may break a lot of current boards. Also I see no need to do > this, as if you do complex stuff in u-boot shell it may is the > wrong way and you have to think about... and I see no big > discussions here about BUGS in our current hush implementation ... > may it makes sense to bring them up and fix? I have been told not to work on the current shell; that it is too old and there is no point in improving it. Since we will be starting afresh anyway, and I do not think that the Hush model is particularly good, I chose to work from a different base. > - Is LIL really so good code, that it is done? Or is there only no community > which develop further? AFAIK there is not too much of a LIL community. The code quality is something I found out after working on it for a while. From a cursory inspection, it was around the same as all the other shells I looked at (no comments, etc). FWIW the current Hush shell does not really handle errors either. For example, on (x)malloc failure, we print and hang. This could easily be done for LIL, but it is not so nice when your language has recursion. So I have tried to add error checking where possible. And of course, Hush ignores missing variables as well. > - Do we really want code, which does no error checking? Commentless code... > > you wrote: >> - There is a serious error handling problem. Most original LIL code never >> checked errors. In almost every case, errors were silently ignored, even >> malloc failures! While I have designed new code to handle errors properly, > > Which really let me think, nobody is interested in this code ... this > sounds like crap... and this brings me to the next point > > - Do we not have the same problem as with hush, if we change LIL code? I think the primary problem with Hush was that we expected to backport updates at all. I think such a core UI feature should not have so many ifdefs in it when no backport was ever made. It is difficult to modify Hush because not only do you have to understand how U-Boot uses some feature, you also have to understand how Busybox uses some feature. And Hush of course has less comments as LIL does (after all patches in this series are applied). > Do you plan to upstream your changes? I don't view it as especially important. I view LIL as a starting point which can be modified to suit U-Boot. It may end up that each individual component is changed in some way, but starting with a working shell has been very helpful for development. > So please do not understand me wrong, I see you invested much time here, > but I see LIL not in the short term as a replacement for hush. > > I would accept to add LIL as an option and we will see, how good it works. That is what I intend to do. > And if we have in lets say 2-3 years more boards which use LIL instead of > hush *and* also active maintained LIL code, we may can think of getting rid > of hush... and may have a "hush compatibility" layer... > > I have no idea of current hush mainline code and how many work it will be > to update U-Boot to a current hush version. But may this would be make more > sense as hush is in active development. Also may to discuss with hush maintainers > to upstream U-Boot changes... this would make in my eyes more sense. AFAICT most of the U-Boot changes are removal of features, workarounds for unimplemented functionality (e.g. anywhere Hush does fork/exec), and some small additions like command repetition which cannot be upstreamed because it would break any semblance of POSIX compatibility. --Sean >> = Why Lil? >> >> When looking for a suitable replacement shell, I evaluated implementations using >> the following criteria: >> >> - It must have a GPLv2-compatible license. >> - It must be written in C, and have no major external dependencies. >> - It must support bare function calls. That is, a script such as 'foo bar' >> should invoke the function 'foo' with the argument 'bar'. This preserves the >> shell-like syntax we expect. >> - It must be small. The eventual target is that it compiles to around 10KiB with >> -Os and -ffunction-sections. >> - There should be good tests. Any tests at all are good, but a functioning suite >> is better. >> - There should be good documentation >> - There should be comments in the source. >> - It should be "finished" or have only slow development. This will hopefully >> make it easier to port changes. >> >> Notably absent from the above list is performance. Most scripts in U-Boot will >> be run once on boot. As long as the time spent evaluating scripts is kept under >> a reasonable threshold (a fraction of the time spend initializing hardware or >> reading data from persistant storage), there is no need to optimize for speed. >> >> In addition, I did not consider updating Hush from Busybox. The mismatch in >> computing environment expectations (as noted in the "New shell" section above) >> still applies. IMO, this mismatch is the biggest reason that things like >> functions and command substitution have been excluded from the U-Boot's Hush. >> >> == lil >> >> - zLib >> - TCL >> - Compiles to around 10k with no builtins. To 25k with builtins. >> - Some tests, but not organized into a suite with expected output. Some evidence >> that the author ran APL, but no harness. >> - Some architectural documentation. Some for each functions, but not much. >> - No comments :l >> - 3.5k LoC >> >> == picol >> >> - 2-clause BSD >> - TCL >> - Compiles to around 25k with no builtins. To 80k with builtins. >> - Tests with suite (in-language). No evidence of fuzzing. >> - No documentation :l >> - No comments :l >> - 5k LoC >> >> == jimtcl >> >> - 2-clause BSD >> - TCL >> - Compiles to around 95k with no builtins. To 140k with builtins. Too big... >> >> == boron >> >> - LGPLv3+ (so this is right out) >> - REBOL >> - Compiles to around 125k with no builtins. To 190k with builtins. Too big... >> >> == libmawk >> >> - GPLv2 >> - Awk >> - Compiles to around 225k. Too big... >> >> == libfawk >> >> - 3-clause BSD >> - Uses bison+yacc... >> - Awk; As it turns out, this has parentheses for function calls. >> - Compiles to around 24-30k. Not sure how to remove builtins. >> - Test suite (in-language). No fuzzing. >> - Tutorial book. No function reference. >> - No comments >> - Around 2-4k LoC >> >> == MicroPython >> >> - MIT >> - Python (but included for completeness) >> - Compiles to around 300k. Too big... >> >> == mruby/c >> >> - 3-clause BSD >> - Ruby >> - Compiles to around 85k without builtins and 120k with. Too big... >> >> == eLua >> >> - MIT >> - Lua >> - Build system is a royal pain (custom and written in Lua with external deps) >> - Base binary is around 250KiB and I don't want to deal with reducing it >> >> So the interesting/viable ones are >> - lil >> - picol >> - libfawk (maybe) > > Very nice overview, thanks! > > bye, > Heiko >
Well, this has been sitting on my hard drive for too long without feedback ("Release early, release often"), so here's the first RFC. This is not ready to merge (see the "Future work" section below), but the shell is functional and at least partially tested. The goal is to have 0 bytes gained over Hush. Currently we are around 800 bytes over on sandbox. add/remove: 90/54 grow/shrink: 3/7 up/down: 12834/-12042 (792) = Getting started Enable CONFIG_LIL. If you would like to run tests, enable CONFIG_LIL_FULL. Note that dm_test_acpi_cmd_dump and setexpr_test_str_oper will fail. CONFIG_LIL_POOLS is currently broken (with what appears to be a double free). For an overview of the language as a whole, refer to the original readme [1]. [1] http://runtimeterror.com/tech/lil/readme.txt == Key patches The following patches are particularly significant for reviewing and understanding this series: cli: Add LIL shell This contains the LIL shell as originally written by Kostas with some major deletions and some minor additions. cli: lil: Wire up LIL to the rest of U-Boot This allows you to use LIL as a shell just like Hush. cli: lil: Document structures This adds documentation for the major structures of LIL. It is a good place to start looking at the internals. test: Add tests for LIL This adds some basic integration tests and provides some examples of LIL code. cli: lil: Add a distinct parsing step This adds a parser separate from the interpreter. This patch is the largest original work in this series. cli: lil: Load procs from the environment This allows procedures to be saved and loaded like variables. = A new shell This series adds a new shell for U-Boot. The aim is to eventually replace Hush as the primary shell for all boards which currently use it. Hush should be replaced because it has several major problems: - It has not had a major update in two decades, resulting in duplication of effort in finding bugs. Regarding a bug in variable setting, Wolfgang remarks So the specific problem has (long) been fixed in upstream, and instead of adding a patch to our old version, thus cementing the broken behaviour, we should upgrade hush to recent upstream code. -- Wolfgang Denk [2] These lack of updates are further compounded by a significant amount of ifdef-ing in the Hush code. This makes the shell hard to read and debug. Further, the original purpose of such ifdef-ing (upgrading to a newer Hush) has never happened. - It was designed for a preempting OS which supports pipes and processes. This fundamentally does not match the computing model of U-Boot where there is exactly one thread (and every other CPU is spinning or sleeping). Working around these design differences is a significant cause of the aformentioned ifdef-ing. - It lacks many major features expected of even the most basic shells, such as functions and command substitution ($() syntax). This makes it difficult to script with Hush. While it is desirable to write some code in C, much code *must* be written in C because there is no way to express the logic in Hush. I believe that U-Boot should have a shell which is more featureful, has cleaner code, and which is the same size as Hush (or less). The ergonomic advantages afforded by a new shell will make U-Boot easier to use and customize. [2] https://lore.kernel.org/u-boot/872080.1614764732@gemini.denx.de/ = Open questions While the primary purpose of this series is of course to get feedback on the code I have already written, there are several decisions where I am not sure what the best course of action is. - What should be done about 'expr'? The 'expr' command is a significant portion of the final code size. It cannot be removed outright, because it is used by several builtin functions like 'if', 'while', 'for', etc. The way I see it, there are two general approaches to take - Rewrite expr to parse expressions and then evaluate them. The parsing could re-use several of the existing parse functions like how parse_list does. This could reduce code, as instead of many functions each with their own while/switch statements, we could have two while/switch statements (one to parse, and one to evaluate). However, this may end up increasing code size (such as when the main language had evaluation split from parsing). - Don't parse infix expressions, and just make arithmetic operators normal functions. This would affect ergonomics a bit. For example, instead of if {$i < 10} { ... } one would need to write if {< $i 10} { ... } and instead of if {$some_bool} { ... } one would need to write if {quote $some_bool} { ... } Though, given how much setexpr is used (not much), this may not be such a big price to pay. This route is almost certain to reduce code size. - How should LIL functions integrate with the rest of U-Boot? At the moment, lil functions and procedures exist in a completely separate world from normal commands. I would like to integrate them more closely, but I am not sure the best way to go about this. At the very minimum, each LIL builtin function needs to get its hands on the LIL interpreter somehow. I'd rather this didn't happen through gd_t or similar so that it is easier to unit test. Additionally, LIL functions expect an array of lil_values instead of strings. We could strip them out, but I worry that might start to impact performance (from all the copying). The other half of this is adding LIL features into regular commands. The most important feature here is being able to return a string result. I took an initial crack at it [3], but I think with this series there is a stronger motivating factor (along with things like [4]). [3] https://patchwork.ozlabs.org/project/uboot/list/?series=231377 [4] https://patchwork.ozlabs.org/project/uboot/list/?series=251013 = Future work The series as presented today is incomplete. The following are the major issues I see with it at the moment. I would like to address all of these issues, but some of them might be postponed until after first merging this series. - There is a serious error handling problem. Most original LIL code never checked errors. In almost every case, errors were silently ignored, even malloc failures! While I have designed new code to handle errors properly, there still remains a significant amount of original code which just ignores errors. In particular, I would like to ensure that the following categories of error conditions are handled: - Running out of memory. - Access to a nonexistant variable. - Passing the wrong number of arguments to a function. - Interpreting a value as the wrong type (e.g. "foo" should not have a numeric representation, instead of just being treated as 1). - There are many deviations from TCL with no purpose. For example, the list indexing function is named "index" and not "lindex". It is perfectly fine to drop features or change semantics to reduce code size, make parsing easier, or make execution easier. But changing things for the sake of it should be avoided. - The test suite is rather anemic compared with the amount of code this series introduces. I would like to expand it significantly. In particular, error conditions are not well tested (only the "happy path" is tested). - While I have documented all new functions I have written, there are many existing functions which remain to be documented. In addition, there is no user documentation, which is critical in driving adoption of any new programming language. Some of this cover letter might be integrated with any documentation written. - Some shell features such as command repetition and secondary shell prompts have not been implemented. - Arguments to native lil functions are incompatible with U-Boot functions. For example, the command foo bar baz would be passed to a U-Boot command as { "foo", "bar", "baz", NULL } but would be passed to a LIL function as { "bar", "baz" } This makes it more difficult to use the same function to parse several different commands. At the moment this is solved by passing the command name in lil->env->proc, but I would like to switch to the U-Boot argument list style. - Several existing tests break when using LIL because they expect no output on failure, but LIL produces some output notifying the user of the failure. - Implement DISTRO_BOOT in LIL. I think this is an important proof-of-concept to show what can be done with LIL, and to determine which features should be moved to LIL_FULL. = Why Lil? When looking for a suitable replacement shell, I evaluated implementations using the following criteria: - It must have a GPLv2-compatible license. - It must be written in C, and have no major external dependencies. - It must support bare function calls. That is, a script such as 'foo bar' should invoke the function 'foo' with the argument 'bar'. This preserves the shell-like syntax we expect. - It must be small. The eventual target is that it compiles to around 10KiB with -Os and -ffunction-sections. - There should be good tests. Any tests at all are good, but a functioning suite is better. - There should be good documentation - There should be comments in the source. - It should be "finished" or have only slow development. This will hopefully make it easier to port changes. Notably absent from the above list is performance. Most scripts in U-Boot will be run once on boot. As long as the time spent evaluating scripts is kept under a reasonable threshold (a fraction of the time spend initializing hardware or reading data from persistant storage), there is no need to optimize for speed. In addition, I did not consider updating Hush from Busybox. The mismatch in computing environment expectations (as noted in the "New shell" section above) still applies. IMO, this mismatch is the biggest reason that things like functions and command substitution have been excluded from the U-Boot's Hush. == lil - zLib - TCL - Compiles to around 10k with no builtins. To 25k with builtins. - Some tests, but not organized into a suite with expected output. Some evidence that the author ran APL, but no harness. - Some architectural documentation. Some for each functions, but not much. - No comments :l - 3.5k LoC == picol - 2-clause BSD - TCL - Compiles to around 25k with no builtins. To 80k with builtins. - Tests with suite (in-language). No evidence of fuzzing. - No documentation :l - No comments :l - 5k LoC == jimtcl - 2-clause BSD - TCL - Compiles to around 95k with no builtins. To 140k with builtins. Too big... == boron - LGPLv3+ (so this is right out) - REBOL - Compiles to around 125k with no builtins. To 190k with builtins. Too big... == libmawk - GPLv2 - Awk - Compiles to around 225k. Too big... == libfawk - 3-clause BSD - Uses bison+yacc... - Awk; As it turns out, this has parentheses for function calls. - Compiles to around 24-30k. Not sure how to remove builtins. - Test suite (in-language). No fuzzing. - Tutorial book. No function reference. - No comments - Around 2-4k LoC == MicroPython - MIT - Python (but included for completeness) - Compiles to around 300k. Too big... == mruby/c - 3-clause BSD - Ruby - Compiles to around 85k without builtins and 120k with. Too big... == eLua - MIT - Lua - Build system is a royal pain (custom and written in Lua with external deps) - Base binary is around 250KiB and I don't want to deal with reducing it So the interesting/viable ones are - lil - picol - libfawk (maybe) I started with LIL because it was the smallest. I have found several issues with LIL along the way. Some of these are addressed in this series already, while others remain unaddressed (see the section "Future Work"). Sean Anderson (28): Add Zlib License cli: Add LIL shell cli: lil: Replace strclone with strdup cli: lil: Remove most functions by default cli: lil: Rename some functions to be more like TCL cli: lil: Convert some defines to enums cli: lil: Simplify callbacks cli: lil: Handle commands with dots cli: lil: Use error codes cli: lil: Add printf-style format helper for errors cli: lil: Add several helper functions for errors cli: lil: Check for ctrl-c cli: lil: Wire up LIL to the rest of U-Boot cli: lil: Document structures cli: lil: Convert LIL_ENABLE_POOLS to Kconfig cli: lil: Convert LIL_ENABLE_RECLIMIT to KConfig test: Add tests for LIL cli: lil: Remove duplicate function bodies cli: lil: Add "symbol" structure cli: lil: Add config to enable debug output cli: lil: Add a distinct parsing step env: Add a priv pointer to hwalk_r cli: lil: Handle OOM for hm_put cli: lil: Make proc always take 3 arguments cli: lil: Always quote items in lil_list_to_value cli: lil: Allocate len even when str is NULL in alloc_value_len cli: lil: Add a function to quote values cli: lil: Load procs from the environment Licenses/README | 1 + Licenses/zlib.txt | 14 + MAINTAINERS | 7 + cmd/Kconfig | 52 +- cmd/nvedit.c | 8 +- common/Makefile | 4 + common/cli.c | 118 +- common/cli_lil.c | 4321 +++++++++++++++++++++++++++++++++++++++++++++ env/callback.c | 4 +- env/flags.c | 4 +- include/cli_lil.h | 202 +++ include/search.h | 2 +- lib/hashtable.c | 5 +- test/cmd/Makefile | 1 + test/cmd/lil.c | 306 ++++ 15 files changed, 5021 insertions(+), 28 deletions(-) create mode 100644 Licenses/zlib.txt create mode 100644 common/cli_lil.c create mode 100644 include/cli_lil.h create mode 100644 test/cmd/lil.c