rand() may call malloc()
thingsquare.com
thingsquare.com
If you're doing your own custom memory management like this, you shouldn't even have a malloc implementation at all. Even newlib is too bloated for your use case. At this point, chances are you're using a trivial subset of the C library and it'd be easy to roll your own. You can import bits and pieces from other projects (I personally sometimes copy and paste bits from PDClib for this). In such a tight embedded project, chances are you don't even have threads; why even pull in that reentrancy code?
Freestanding C code with no standard library isn't scary. If you need an example, look at what we do for m1n1:
https://github.com/AsahiLinux/m1n1/tree/main/src
In particular, this is the libc subset we use (we do have malloc here, which is dlmalloc, but still not enough of libc to be worth depending on a full one):
It’s a trap that people fall into to think that it’s easy to roll your own. It depends on what, exactly, you are rolling, what resources you have, etc. Maybe I need a couple math functions, a decent implementation of memset/memcpy/etc, and having the C library at my disposal gives me those things.
The idea that you throw out Newlib just because one function pulled in malloc seems unjustifiable to me.
On the other hand, I think it’s quite normal to want your own PRNG.
Ooh, I can answer this one! It turns out that I know what else in the C library can give you trouble. Newlib is open-source. For embedded projects, I find myself reading the source code to Newlib, and sometimes looking at the disassembly to double-check what version of a function I’m getting.
If I had gotten burned by having malloc included when I didn’t wanted (never happened to me personally), I would consider running "ar d" to remove it from the copy of the library I’m using. It’s pretty easy to modify static libraries.
> For me I’ve found GitHub Copilot great for filling in basic stubs for C stdlib APIs.
I might want a decent implementation of snprintf, might want some decent implementation of memcpy/memset/memmove. I’ve implemented all of these myself, but it’s a pain, and I generally would rather grab Newlib rather than trust Copilot.
CC0 isn't a viral license, you have literally no obligations if you use it: no attribution, no license compatibility worries, no relicensing issues, not even a need to mention it at all.
> Can I apply a Creative Commons license to software?
> We recommend against using Creative Commons licenses for software. Instead, we strongly encourage you to use one of the very good software licenses which are already available. We recommend considering licenses listed as free by the Free Software Foundation and listed as “open source” by the Open Source Initiative.
> Unlike software-specific licenses, CC licenses do not contain specific terms about the distribution of source code, which is often important to ensuring the free reuse and modifiability of software. Many software licenses also address patent rights, which are important to software but may not be applicable to other copyrightable works. Additionally, our licenses are currently not compatible with the major software licenses, so it would be difficult to integrate CC-licensed work with other free software. Existing software licenses were designed specifically for use with software and offer a similar set of rights to the Creative Commons licenses.
https://creativecommons.org/faq/#can-i-apply-a-creative-comm...
> Also, the CC0 Public Domain Dedication is GPL-compatible and acceptable for software. For details, see the relevant CC0 FAQ entry
following that link: https://wiki.creativecommons.org/wiki/CC0_FAQ#May_I_apply_CC...
> May I apply CC0 to computer software? If so, is there a recommended implementation?
> Yes, CC0 is suitable for dedicating your copyright and related rights in computer software to the public domain, to the fullest extent possible under law. Unlike CC licenses, which should not be used for software, CC0 is compatible with many software licenses, including the GPL. However, CC0 has not been approved by the Open Source Initiative and does not license or otherwise affect any patent rights you may have.
Particularly the license has been an issue getting through legal in older companies where it might not be whitelisted. Particularly with their FAQ still saying not to use it for software.
The considerations are very different from, say, developing apps for an operating system. There is a gradient between those, and the software development considerations shift as you move along. Most people doing embedded development defer to libraries way too early - usually because they're either pure hardware people who haven't learned low-level firmware bring-up and rely on vendor tooling, or people from a higher level software background who find the idea of bare metal scary.
You can see an example of this gradient in the Asahi Linux boot chain:
- m1n1: bare metal, no threads (barebones SMP support for research only), statically linked, no device model, not readily portable, 64-bit only, assumes everything is an M1/Apple Silicon, embedded libc subset, vendored (C: dlmalloc, printf, decompression algorithms, libfdt) or git submodule (Rust: FAT32 implementation) dependencies, single-purpose NVMe & FAT32 implementations (no abstraction).
- u-boot: bare metal, no threads, statically linked, basic device model, portable, embedded libc subset, vendored dependencies, basic filesystem & block device abstraction.
- GRUB: runs on EFI environment, no threads, dynamically linked modules, portable, filesystem & block device abstractions, no actual modifications for Apple Silicon (we use vanilla bins)
- Linux kernel: bare metal, complex thread model, dynamically linked modules, rich device model, portable, embedded libc subset, vendored dependencies, rich filesystem and block device abstractions.
- Linux userspace: you know this.
Notice how none of the components before userspace use a full fat libc, and only have minimal dependencies which are carefully controlled - and this is on a system with gigabytes of RAM.
Personally, I would only use newlib on systems which are roughly equivalent, in terms of model/software stack, to a full desktop OS. That is, embedded systems with at least a threaded RTOS and a filesystem abstraction, possibly a BSD-style sockets layer. Anything smaller than that (no threads? lwip callback style sockets? no filesystem?), you're better off rolling your own.
Also, this seems to be suggesting they are in fact importing all of newlib with its malloc code onto their code which is...kind of a waste. Again, if they could throw that re-entrancy switch somewhere they'd probably eek out a KB or so for the code on their eeprom or w/e holds it. Again, the better solution isn't to keep using newlib with that shit turned on (lol) but then implement your own rand() which will take up a few more bytes in addition to the newlib rand() that you won't use, turning off the re-entrancy is all around the right solution, assuming they want to keep using newlib and won't roll their own (which is by far even better assuming they have the will for that and the time, although as you point out, you don't need a lot of the stdlib, basically most of stdio is out, str to int converters, and so on, it might be worth a future investment to have their own mini library).
For some reason the blog lists the source for rand_r, to which the caller supplies the state rather than using global state.
I wonder if they'll run into this with any of the non-reentrant C functions (strtok, I'm looking at you). It makes their conclusion of "we stopped using rand()" a bit wanting.
I mean, it's great that they stopped using rand(), that's a good move, and pragmatic given their issue, it just feels like it's a really surface level conclusion.
Something you do have to watch out for regardless is accidental promotions of floats to doubles. C loves float promotion, and if you're not careful (and don't use the special compiler options) it's easy to turn a one-cycle FPU operation into a hundred-cycle CPU function call.
I keep thinking there ought to be a better language for bare-metal microcontroller programming, but the demand for it is so small I'm not sure who would bother supporting it.
I’d love to see Ada get “modernized” where the syntax could fundamentally change but the ideas are similar. Being able to explicitly say the range of values is pretty cool, for example.
This is one of the better intros: http://cowlark.com/2014-04-27-ada/index.html
One of my favorite lesser-advertised features is the ability to return arbitrary-length arrays or sum types from functions without heap allocation due to the use of a secondary stack.
I’m not sure if it would meet your requirements or not.
Which in this instance also means that floats stay floats, doubles stay doubles and u8 stays u8 unless you explicitly convert. If you're now asking what happens when you add a float to a double: that's a compiler error, you have to explicitly cast.
- the standard library
- jemalloc (this is no longer the default, but is still a factor in people's perception about binary size because it used to be)
- debug symbols
- unwinding support for panics
All of these can be turned off for use cases like embedded where binary size is important and you'll then get binaries of comparable size to those produced by C compilers.
You can’t just use the broader ecosystem willy nilly, and if you want truly small stuff, you have to know how to coax the compiler from time to time. But that’s just always going to be the case.
A lot of the rest of the fat is from things like debugging symbols bounds checks that aren't included when building in release mode.
This lets you use dynamically sized buffers, depending on the particular configuration present at startup. Very handy to not need to build many different configs and maintain separate binary images (and keep track so that you never update hardware with the wrong image). The disadvantage is that you can't just remove malloc() in such a design.
- They've got an embedded system with all static allocation (they do mention having a dynamic allocator though)
- They've recently found a stack corruption crash which was traced back to rand() calling malloc() which is both unexpected and also malloc should never be called in the system at all
- They traced it back to their usage of newlibc configured to add reentant suppose for c functions that don't don't support it, and this support uses malloc, so when they call rand() this results in a call to malloc()
- A recent tooling update caused them to be using newlibc built this way; they previously were using newlibc configured without this feature
- Their solution is to not use rand() and instead use a different prng, and to write a tool that detects use of malloc() and fails the build
We did, and it was pretty slow despite all the microoptimizations (for example we used fixed point math). It was at the time when hyperthreaded CPUs were introduced and my friend added support for multithreading - 1 thread would draw 1 half of the screen. It broke our code and we found out rand() wasn't thread-safe.
So being the inexperienced dumbasses we were - we added locks around the rand() calls :). Which made the whole multithreading useless but we didn't realize it then :) What we should do is implement rand() on local variables, it's like 3 lines of code :)
I think part of the message here is to not be afraid to come off as inexperienced as an engineer.
This particular call to rand() was written by a person with decades of experience with writing code like this. This person maybe isn't a starninjarock developer, but definitely experienced. Who did it? Let's git blame the code:
13a3029435b core/lib/random.c (adamdunkels 2009-02-11 11:09:59 +0000 52) return (unsigned short)rand();
The article was written Adam Dunkels who is certainly not without creds in the embedded world. Why whould he show the code to rand_r() in an article about rand()? So confused now.
This is the code of the rand() function, which looks familiar:
That has to count as at least a typo, but I think it's a bigger editing-type problem.
> The stack memory is somewhat tricky to allocate, because its maximum size is determined at runtime.
>
> There is no silver bullet: we can’t predict it. So we need to measure it.
GCC has -Wstack-usage=BYTES to warn you if a single function uses more than BYTES of stack space (VLAs and alloca not included), which admittedly isn't too useful if your function calls another...
I'm sure I'm not finished discovering fun stuff.
CHR RAM (like graphics ram, sort of) is a different story perhaps, but at least for the game logic and some sprite manipulation, yeah 2KB for an 8bit game is plenty. I think programming in C (which requires a stack, also probably requires floats which the 6502 has no native support for and would require implementation by the compiler) adds a lot of convenience but the overhead is too much for a NES, although there are libraries and tools for NES C programming out there.
Stop.
Writing blog posts.
Like Linkedin posts.
Like this.
It makes them.
Hard to read.
Annoying.
How annoying?
Very annoying.
uint64_t lemur64(void) {
static uint128_t s = 2131259787901769494;
return (s *= 15750249268501108917ull) >> 64;
}
master jart@nightmare:~/cosmo2$ o/examples/getrandom.com -b lemur64 | RNG_test stdin64 -seed 2131259787901769494
RNG_test using PractRand version 0.95
RNG = RNG_stdin64, seed = 2131259787901769494
test set = core, folding = standard (64 bit)
rng=RNG_stdin64, seed=2131259787901769494
length= 512 megabytes (2^29 bytes), time= 3.2 seconds
no anomalies in 229 test result(s)
rng=RNG_stdin64, seed=2131259787901769494
length= 1 gigabyte (2^30 bytes), time= 7.5 seconds
no anomalies in 246 test result(s)
rng=RNG_stdin64, seed=2131259787901769494
length= 2 gigabytes (2^31 bytes), time= 15.0 seconds
no anomalies in 263 test result(s)
rng=RNG_stdin64, seed=2131259787901769494
length= 4 gigabytes (2^32 bytes), time= 28.6 seconds
no anomalies in 279 test result(s)
rng=RNG_stdin64, seed=2131259787901769494
length= 8 gigabytes (2^33 bytes), time= 55.7 seconds
no anomalies in 295 test result(s)
rng=RNG_stdin64, seed=2131259787901769494
length= 16 gigabytes (2^34 bytes), time= 108 seconds
no anomalies in 311 test result(s)
uint64_t dilbert_rand(void) {
return 9;
}
int rand(void) {
static int gorp;
gorp = (gorp + 625) & 077777;
return gorp;
}While multiplicative congruential PRNGs with a 32-bit state are poor, those with an 128-bit state, like yours, may be quite good.
However, for any application that needs pseudo-random numbers, you must have a good understanding of its requirements, in order to be able to choose the right PRNG.
For example, when the random numbers are used to choose the coordinates of random points in a multi-dimensional space, simple congruential PRNGs are guaranteed to show some correlations between the coordinates that should have been independent, though for a PRNG with an 128-bit state, unless it uses a poorly chosen multiplicative constant, the correlations will appear only for rather long sequences.
There is another kind of PRNG, which has exactly the same speed as yours, but which produces much better pseudo random sequences, the MLFG (Multiplicative Lagged Fibonacci Generator, 1984). Unlike yours, it is a non-linear generator, which is the reason for the good quality. While the speed is the same, it uses a larger state.
The choice of a PRNG can be important in 2 cases, for embedded microcontrollers, like in the parent article, and for applications which have to generate a huge amount of random numbers, e.g. billions of numbers per second.
Otherwise, there is a simpler choice, just use AES in counter mode as the PRNG.
Even when cryptographic strength is not needed, it does not hurt. The AES speed on all modern CPUs is not much lower than that of the fastest PRNGs, and only very few applications need faster PRNGs than AES. Moreover, a PRNG in counter mode has many advantages over the PRNGs based on a recurrence formula. It is possible to access quickly any arbitrary point in the random sequence. It is possible to split the random sequence in any number of subsequences, which can be computed in parallel and which are guaranteed to be uncorrelated, which is important in many multi-threaded programs.
btw I never needed a malloc for my baremetal firmwares so far. 10KB just for a stack and heap? crazy, that's way too much. recursion is forbidden anyway, and sbrk not provided. some unfortunate libc's need that, but MISRA will not be happy.
int
rand_r (unsigned int *seed)
{
long k;
long s = (long)(*seed);
if (s == 0)
s = 0x12345987;
k = s / 127773;
s = 16807 * (s - k * 127773) - 2836 * k;
if (s < 0)
s += 2147483647;
(*seed) = (unsigned int)s;
return (int)(s & RAND_MAX);
}
long s = (long)(*seed);Likewise
if (s < 0) s += 2147483647;
Overflow/underflow is UB in this case, and who says it is 32 bit in the first place?
The sizes of "unsigned long" and of "long" are unknown, but they are at least 32 bit.
Had "unsigned long" been used, modular arithmetic without overflow would have been used, which was the intention of the code.
Of course the condition of the test must also be changed for an "unsigned long".
As it is written here, it is completely wrong. If this program would be compiled with the correct "-fsanitize=undefined -fsanitize-undefined-trap-on-error" options, which should be always used for any C/C++ program, unless there are good reasons to do otherwise, then the program will be aborted at one of the the first invocations of the function.
The constants 16807 and 127773 are chosen so that their product is 2147480811, which is smaller enough than 2^31 to prevent overflows in the line:
s = 16807 * (s - k * 127773) - 2836 * k;
where s is known to be positive and less than 2^31, and (s - k * 127773) is the remainder from the division of s by 127773, and k is the quotient of that division.
Adding 2^31 - 1 to a negative 32-bit number cannot produce an overflow in:
if (s < 0) s += 2147483647;
So both the parent comment and my initial confirmation were wrong, the library code is correct. Initially I have replied too quickly, without reading the source. because most such congruential generators are written to use modular arithmetic, while this one has been carefully modified to obtain an equivalent result using integer arithmetic (which also makes it much slower than what can be done with modular arithmetic, so the reason for this is unclear).
The only thing that can be criticized is the lack of a comment emphasizing that those constants cannot be modified haphazardly, otherwise integer overflows are certain.
So your test has verified that the code is correct, so no overflows happened.
Your large seed becomes -1 after conversion to long on a 32-bit system, or it retains its value on a 64-bit system.
For different reasons, in both cases there are no overflows (on a 64-bit system, long is 64-bit, so overflows would have been avoided even with much wider allowable ranges for the constants; the constants are optimized for systems with 32-bit longs, where they are just below the limit for overflows).
Some other values that are either negative or larger than 2^31 may cause overflows, but they are illegal for this function.
Is this not what I was referring to? I would like to learn more, I think we have the same reasoning, but I am bad at explaining. It think perhaps it could be a good learning experience to HN if you could say exactly what lines you believe are wrong.
You don't want to use malloc? Don't have malloc.
However this approach works only in single-threaded programs. In multi-threaded programs, the static variables are clobbered when invocations of the function from different threads are interleaved.
The correct method to make the standard C library reentrant is to replace all the functions that use static variables with reentrant functions having one extra parameter, which typically use the old name of the function with the suffix "_r".
This has been done, but this means that if you have an old single-threaded program, when you want to make it multi-threaded you must search the program source for all bad standard library functions and replace them with good functions.
Newlib offers an optional facility to avoid the editing of the source files when making a conversion to multi-threading, by replacing all the static variables with dynamically-allocated variables, which will be distinct in different threads.
This feature should better be avoided, because the newer reentrant standard functions also correct other problems, in many cases.
An exception is precisely the "rand_r" function, which is supposed to replace "rand", but which has been wrongly defined, with an inappropriate size of the state parameter.
None of the ancient functions "rand", "rand_r", "srand", "random" or "srandom" should be used in any remotely serious application of random numbers.
There are a huge number of good PRNGs for which the source code is freely available.