11 ms·
rand() may call malloc()
- zgs 5y agoRemove malloc from your libc and catch this entire family of problems at link time.
- MarkSweep 5y agoThis is the correct answer. If you are really doing what the article says (allocating all memory at compile time), why is malloc() being linked in at all?
- renox 5y agoWhat we do at day job is to have a 'whitelist' of all malloc callers which is checked by the CI.
- SAI_Peregrinus 5y agoSometimes you want to allow dynamic allocation at application startup, but never thereafter. Free happens implicitly when the system reboots. 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.
- chrsig 5y agoSo...it wasn't really rand() at fault here, it was some reentrancy library that newlib uses... 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.
- raggi 5y agocame here to raise the same thing, it's odd that this rand was allocating. it seems a little odd to be fixing reentry in rand() and not rand_r() when rand is already so bad anyway. I'm not sure what's worse between doing this reentrancy dance and dropping the taocp magic number accidentally if the static isn't seeded (as in musl). rand is bad, stop using rand was the right answer in any case.
- piker 5y agoTo be fair they did say at the end they added a regression test to look for malloc calls in the binaries.
- marcan_42 5y agoThe solution isn't to stop using rand(). The solution is to stop using newlib. 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 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): https://github.com/AsahiLinux/m1n1/tree/main/sysinc https://github.com/AsahiLinux/m1n1/tree/main/sysinc
- deleted 5y ago[deleted]
- kevin_thibedeau 5y agoNewlib can be configured without reentrancy support and you can do that in a multi-tasking environment while still using their malloc provided you implement some locking callbacks. This saves a ton of static state for non-reentrant library functions you're unlikely to ever need and can replace with safe variants if you do need them.
- marcan_42 5y agoWhen you are working in a tight embedded system, instead of fighting to slim down a library that is designed to scale to significantly larger systems, it makes much more sense to start from zero and add only what you need. You also shouldn't update your dependencies blindly, ever (even updating the compiler should be done with care). 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.
- AdamH12113 5y agoThis sort of thing is why I prefer to leave the C standard library out of my microcontroller code altogether. It keeps me from having to worry about what PC-centric assumptions they may be making under the hood, and they're often a bit bloated anyway. 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.
- SnowHill9902 5y agoThat’s more about the compiler than C.
- traes 5y agoMy friend, the compilers are implementing that behavior based on the C standard, which is the literal definition of what C is. It's absolutely about C.
- chrisseaton 5y agoWhat do you think the compiler should be doing differently? Is there’s no FPU support then what is the alternative?
- languageserver 5y agoit is one of the unfortunate things about C, a language I love and defend dearly, is that on one hand it makes few assumptions about the system and is "bare metal" enough to shoot yourself, but at the same time it makes no assumptions about what is now agiven on modern systems
- legalcorrection 5y agoYou probably know, but for the benefit of the others, at least some compilers support warning for that with -Wdouble-promotion.
- bombcar 5y agoJust use dilbert_rand(). Threadsafe reentrant and doesn’t allocate.
- SeanLuke 5y agoHis solution is to use a PCG generator? As far as I know its designer withdrew submission of a journal article after negative reviews and has never resubmitted one. And this doesn't look good: https://pcg.di.unimi.it/pcg.php https://pcg.di.unimi.it/pcg.php
- jwmerrill 5y agoO’Neil has responded to those criticisms here: https://www.pcg-random.org/posts/on-vignas-pcg-critique.html https://www.pcg-random.org/posts/on-vignas-pcg-critique.html
- oh_sigh 5y agoI agree with the article that a MWC generator could be better, but for their use case, a really crappy rand() might be more than adequate.
- jart 5y agoIf you have enough hardware to do multiplication and aren't doing cryptography, you can always use my random number generator instead. uint64_t lemur64(void) { static uint128_t s = 2131259787901769494; return (s *= 15750249268501108917ull) >> 64; } The test suite on that page says it's fine. 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) There's also Scott Adams' prng: uint64_t dilbert_rand(void) { return 9; } Another one of my favorites is UNIXv6: int rand(void) { static int gorp; gorp = (gorp + 625) & 077777; return gorp; }
- jesprenj 5y agoIf malloc() damages the running system, why even implement it in the standard library?
- Animats 5y agoThis is why Rust has both "std" and "core". "core" lacks allocation capability.
- tedunangst 5y agoMaybe in an low quality implementation. rand() is not defined to have error conditions, and definitely not assert when malloc fails.
- gojomo 5y agoIs this thus a `malloc()` without a matching `free()`?
- saagarjha 5y agoYes. It lives forever, so this isn't a problem.
- naoqj 5y agoJesus how annoyingly written.
- languageserver 5y agoIt reads like a marketing blog post. Written as if this was one of those "I dissambled a printer driver to discover a race condition that could cause privilege escalation and I made a CVE that saved millions of PCs around the world" or something, but really it is just someone who took the time to read 10 lines of badly written C.
- Laura69 5y ago[dead]
- ajuc 5y agoWe had a team project at university to write some graphic demo in 3d from scratch (no open gl, no fancy graphic libraries, just plotting pixels onto screen). 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 :)
- matthews2 5y agoThere's also rand_r() if you didn't want to write that three lines of code :)
- SourceParts 5y agoCan you. Stop. Writing blog posts. Like Linkedin posts. Like this. It makes them. Hard to read.
- urbandw311er 5y agoIt’s possible the architect of the article is actually a marketeer who wanted to publicise the company and its “careful approach” to IOT. Be careful what you wish for! Now your engineers just look a little inexperienced as a result.
- unwind 5y agoI had to check the author ...learned that Thingiverse are Swedish, based in Stockholm even. 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.
- AlotOfReading 5y agoYou shouldn't be confused if you read the article. The actual PRNG is implemented in rand_r() and is the first place most people would look. The issue is in the reentrant wrapper in rand().
- unwind 4y agoI seem to be catching downvotes, but I did read the article. The text right before the rand_r() code box reads: 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.
- adunk 5y agoOP here. 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(); (Yep, that's me!)
- furyofantares 5y agoThe article contains a fair bit of fluff that may be aimed at developers without familiarity with embedded systems or I guess C, I'm not exactly sure what's with the tone but the short of it is: - 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
- matthews2 5y ago> 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. When you're extremely memory constrained, you should probably know the max stack depth at different points in your program. 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...
- deleted 5y ago[deleted]
- pif 5y agoIf you are developing against a supposed implementation, rather than the published interface, you are wrong. rand is not the culprit, newlib is not the culprit: you are. You don't want to use malloc? Don't have malloc.
- ufo 5y agoDoes anyone know why the reentrancy layer needed malloc in the first place? I didn't understand that part.
- saagarjha 5y agoIt's used to store internal random state.
- touisteur 5y agoI know it's offtopic, but adding perf probes to glibc's malloc in a running system was quite revealing: - qsort calls malloc - and qsort is used a lot in glibc internal functions such as gethostbybame so... Yeah. - snprintf can call malloc too I'm sure I'm not finished discovering fun stuff.
- deleted 5y ago[deleted]
- togaen 5y agoInteresting article, but, man, incredibly annoying writing style. It reads like a LinkedIn post. Use normal sentence/paragraph structure and say what you’re going to say.
- deleted 5y ago[deleted]
- aaaaaaaaaaab 5y agoI don’t get it. Why does newlib malloc in rand() instead of just storing the global state in a static variable?
- freemint 5y agoIt didn't.
- adrian_b 5y agoIn the traditional standard C library, there are many functions which, in order to be invoked with less parameters, use some static variables. 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.
- jffhn 5y agoAnd in Java, Math.cos(double) might do allocation as well, for large angles reduction. In Jafama I took care to avoid that, by encoding the quadrant in two useless bits of reduced angle exponent.
- languageserver 5y agoint 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); } Who on this green Earth wrote this?? long s = (long)(*seed);
- m55au 5y agoWhat is wrong with that?
- languageserver 5y agoThe size of a long is not defined, and is platform dependent. It may be the size of int. Likewise if (s < 0) s += 2147483647; Overflow/underflow is UB in this case, and who says it is 32 bit in the first place?
- deleted 5y ago[deleted]
- adrian_b 5y agoThat code is indeed wrong, but the error consists in using "long" instead of "unsigned long". 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.
- m55au 5y agoThose compilation options did not make the program abort for me nor am I getting any warnings (at least not with -Wall -Wextra), even when changing all longs to ints in the above code, in order to investigate the case when sizeof (int) == sizeof (long) == 4. Setting *seed = 4294967295 has also no effect. What am I missing?
- h2odragon 5y agoWonder what other joyous opportunities for unforeseen functionality they're unknowingly baking into their "IoT" devices.
- noobermin 5y agoAs someone who dabbles with NES programming, 10KB is quite a lot of ram for me. NES programming is almost always in 6502 asm and at least when I do it I don't even need the stack. Generally people do not use it for storage, they use the stack just for function calling, and generally uses just a fraction of the zero page for the most part. Instead, every subroutine either gets its own variables somewhere in memory or you use zero page and have to be careful that the interrupt handlers do not disrupt the parts of zero page that other routines might use. It's a lot harder perhaps but it does force you to be more intentional with your memory usage. I'll admit I've never coded any like crazy demos (yet) but programming in this way, I've yet to use anywhere near to the full 2KB for standard ram the NES has. 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.
- Carter69 4y ago[flagged]