Wandering Thoughts

Reading the POSIX standard for Unix functions is not straightforward

I recently wrote about exploring munmap() on page zero, and in the process looked at the POSIX specification for munmap(). One of my discoveries about the practical behavior of Unixes here is that OpenBSD specifically disallows using munmap() on address space that isn't currently mapped (see munmap(2)). In my entry, I said that it wasn't clear whether POSIX strictly authorized this behavior, although you could put forward an interpretation where it was okay.

In a comment, Jakob Kaivo put forward the view that POSIX permitted this and any other behavior for when munmap() was applied to unmapped address space because of a sentence in the end of the Description:

The behavior of this function is unspecified if the mapping was not established by a call to mmap().

At first reading this seems clear. But wait, it's time to get confused. Earlier in the same description of munmap()'s behavior, POSIX clearly says that it can be used if there is no mapping:

[...] If there are no mappings in the specified address range, then munmap() has no effect.

(Note that 'has no effect' is different from 'unspecified'.)

POSIX doesn't require that this not raise an error, but you can read its description of when you can get EINVAL to require that you don't (some of the time). Assuming addr is aligned and len is not zero, you get EINVAL if some of the address space you're unmapping is 'outside the valid range for the address space of a process', and perhaps implicitly not otherwise. And then you have the question of what POSIX intended here by saying 'a process space' instead of 'the (current) process'.

One of the things we can see here is that it's hard for non-specialists to truly read and understand the POSIX standards. Both Jakob Kaivo and I are at least reasonably competent C and Unix programmers and we've both attempted to read a reasonably straightforward POSIX specification of a single function, yet we've wound up somewhere between disagreeing and being uncertain about what it allows.

This is a useful lesson for me to remember any time I'm tempted to appeal to a POSIX standard for how something should work. POSIX standards are written in specifications language, and if they're not completely clear I should be cautious about how correct I am. Probably I should be cautious even if they seem perfectly clear.

(And anyway, the actual behavior of current Unixes matters more than what POSIX says. A POSIX specification is merely a potential lower bound on behavior, especially future behavior. If a Unix does something today and that something is required by POSIX, the odds are good that it will keep doing that in the future.)

PS: My interpretation of the unspecified behavior versus 'no behavior' here is that POSIX is saying that it's unspecified what happens if you munmap() legitimate address space that wasn't obtained through your own mmap(). For instance, if you munmap() part of something that you got with malloc(), anything goes as far as POSIX is concerned. It might work and not produce future problems, it might have no effect, it might kill your program immediately, and it might cause your program to malfunction or blow up in the future.

Exploring munmap() on page zero and on unmapped address space

Over in the Fediverse, I ran across an interesting question on munmap():

what does `munmap` on Linux do when address is set to 0? Somehow this succeeds on Linux but fails on FreeBSD. I'm assuming the semantics are different but cannot find any reference regarding to such behavior.

(There's also this additional note, and the short version of the answer is here.)

When I saw this, I was actually surprised that munmap() on Linux succeeded, because I expected it to fail on any address range that wasn't currently mapped in your process and page zero is definitely not mapped on Linux (or anywhere sane). So let's go to the SUS specification for munmap(), where we can read in part:

The munmap() function shall fail if:

[EINVAL]

Addresses in the range [addr,addr+len) are outside the valid range for the address space of a process.

(Similar wording appears in the FreeBSD munmap() manpage.)

When I first read this wording, I assumed that this meant the current address range of the process. This is incorrect in practice on Linux and FreeBSD, and I think in theory as well (since POSIX/SUS talks about 'of a process', not 'of this process'). On both of those Unixes, you can munmap() at least some unused address space, as we can demonstrate with a little test program that mmap()s something, munmap()s it, and then munmap()s it again.

The difference between Linux and FreeBSD is in what they consider to be 'outside the valid range for the address space of a process'. FreeBSD evidently considers page zero (and probably low memory in general) to always be outside this range, and thus munmap() fails. Linux does not; while it doesn't normally let you mmap() memory in that area, for good reasons, it is not intrinsically outside the address space. If I'm reading the Linux kernel code correctly, no low address range is ever considered invalid, only address ranges that cross above the top of user space.

(I took a brief look at the relevant FreeBSD code in vm_mmap.c, and I think that it rejects any munmap() that extends below or above the range of address space that the process currently has mapped. This is actually more restrictive than I expected.)

In ultimately unsurprising news, OpenBSD takes a somewhat different interpretation, one that's more in line with how I expected munmap() to behave. The OpenBSD munmap() manpage says:

[EINVAL]

The addr and len parameters specify a region that would extend beyond the end of the address space, or some part of the region being unmapped is not part of the currently valid address space.

OpenBSD requires you to only munmap() things that are actually mapped and disallows trying to unmap random sections of your potential address space, even if it falls within the bottom and top of your address space usage (where FreeBSD would allow it). Whether this is completely POSIX compliant is an interesting but irrelevant question, since I doubt the OpenBSD people would change this (and I don't think they should).

One of the interesting things I've learned from looking into this is that Linux, FreeBSD, and OpenBSD each sort of have a different interpretation of what POSIX permits (assuming I'm understanding the FreeBSD kernel code correctly). The Linux interpretation is most clearly permitted, since it allows munmap() on anything that might potentially be mappable under some circumstances. OpenBSD, if it cares, would likely say that the 'valid range for the address space of a process' is what it currently has mapped and so their behavior is POSIX/SUS compliant, but this is clearly pushing the interpretation in an unusual direction from a narrow specification style reading of the wording (although it is the behavior I expected). FreeBSD sort of splits the difference, possibly for implementation reasons.

PS: The Linux munmap() manpage doesn't even talk about 'the valid address space of a (or the) process' as a reason for munmap() to fail; it only talks abstractly about the kernel not liking addr or len.

Sidebar: The little test program

Here's the test program I used.

#include <sys/mman.h>
#include <stdio.h>
#include <errno.h>
#include <string.h>

#define MAPLEN  (128*1024)

int main(int argc, char **argv)
{
  void *mp;

  puts("Starting mmap and double munmap test.");
  mp = mmap(0, MAPLEN, PROT_READ, MAP_ANON|MAP_SHARED, -1, 0);
  if (mp == MAP_FAILED) {
    printf("mmap error: %s\n", strerror(errno));
    return 1;
  }
  if (munmap(mp, MAPLEN) < 0) {
    printf("munmap error on first unmap: %s\n", strerror(errno));
    return 1;
  }
  if (munmap(mp, MAPLEN) < 0) {
    printf("munmap error on second unmap: %s\n", strerror(errno));
    return 1;
  }
  puts("All calls succeeded without errors, can munmap() unmapped areas.");
  return 0;
}

I think that it's theoretically possible for something like this program to fail on FreeBSD, if our mmap() established a new top or bottom of the process's address space. In practice it's likely that we will mmap() into a hole between the bottom of the address space (with the program text) and the top of the address space (probably with the stack).

The Unix divide over who gets to chown things, and (disk space) quotas

One of the famous big splits between the BSD Unix world and the System V world is whether ordinary users can use chown (the command and the system call) to give away their own files. In System V derived Unixes you were generally allowed to; in BSD derived Unixes you weren't. Until I looked it up now to make sure, I thought that BSD changed this behavior from V7 and that V7 had an unrestricted chown. However, this turns out to be wrong; in V7 Unix, chown(2) was restricted to root only. The manpage even says why:

[...] Only the super-user may execute this call, because if users were able to give files away, they could defeat the (nonexistent) file-space accounting procedures.

(V7 didn't have any direct support for disk quotas or file space accounting, although you could put together various things to at least monitor who was using how much space by sweeping over the filesystem.)

In 4.2 BSD, UCB CSRG added disk quotas (I believe as part of the new 4.2 BSD Fast File System), and so they kept the restriction on chown(2). Now that they had real disk quotas, the threat of undergraduates and other people defeating them with chown was quite real and had to be avoided.

(4BSD didn't have disk quotas but it did have a quot(8) command to analyze the filesystem and tell you per-user usage information, so this area was on CSRG's collective minds for a while. It operated by scanning the raw filesystem through the disk, per quot.c.)

On the System V side, the restriction on chown(2) appears to have been lifted in System III (32V Unix still has it). I don't know why it was removed, but System III has no disk quota system and the change is clearly deliberate, as the chown(2) manpage has been updated to document the new state of affairs. This was carried through to System V, where it became well known (and common, as System V spread).

All of this left POSIX with a little bit of a mess, which POSIX solved by allowing both behaviors in the POSIX chown() specification. In fact POSIX goes further than a system wide choice; things may differ on a path by path basis, with some paths permitting normal people to give away their files and some not.

(In fact the 'rationale' section of the POSIX chown() specification has a thorough recounting of the historical differences that led to the situation, and confirms that normal UIDs being allowed to give away ownership was a System III addition.)

Pretty much all common modern Unixes have come down on the BSD side of this divide. The *BSDs inherited the original V7 and 4.2 BSD restriction on chown(2), and Linux copied or adopted it. Illumos inherited from System V R4 through Solaris, and appears to have a chown(2) that by default follows the System V behavior of allowing anyone to give away files; however, its chown(2) manpage documents a system wide way to turn this off, among other options.

(It's my view that a restricted chown(2) is the right choice even if you ignore disk quota issues, but that's another entry.)

Sidebar: How to safely defeat disk quotas by chowning away your files

Because this may not be obvious, let's suppose that you are an undergraduate on a system that implements disk quotas (based on file ownership) but permits you to chown them to other people. Then you can get around your disk quota as follows:

1. Make a restricted directory somewhere. Perhaps you can call it $HOME/assignments; no one is going to fault you for making that only accessible by you.

2. Create your (big) files in this restricted directory or a sensible subdirectory of it, making them world readable (or perhaps only group readable to a group you're in), and executable if necessary. You can also make them writeable if you need to.

3. Pick a victim user, let's call him barney. Chown all of these files to barney, who suddenly gets charged for their space usage.

You retain access to these files although barney now owns them, because giving them away didn't change their file permissions in any important way. Barney doesn't have any access to them because they're hidden away inside an inaccessible directory; standard Unix gives normal users no way to find such files or to manipulate them once they're found. And if you need to make the evidence go away or just change things around, you can delete the files because you still own the directories they're in.

If you use GNU Grep on text files, use the -a (--text) option

Today, I happened to notice that one of my email log scanning scripts wasn't reporting on a log entry that I knew was there (because another, related script was reporting it). My log scanning script starts out with a grep to filter out some things I don't want to include:

grep -hv 'a specific pattern' "$@" | exigrep '...' | [...]

I had all sorts of paranoid thoughts about whether I had misunderstood exactly what the -v option did, or if exigrep was doing something peculiar, and so on. But eventually I ran the grep itself alone on the file, piped to less, and jumped to the end in less because I happened to know that the missing entry was relatively late in the file. What I was expecting to happen is that the grep output would just stop at some point. What I actually found was simple:

2020-04-13 16:07:06 H=(111iu.com) [223.165.241.9] [...]
2020-04-13 16:07:07 unexpected disconnection [...]
Binary file /var/log/exim4/mainlog matches

Ah. Yes. How helpful. While reading along in what it had up until then thought was a text file, GNU Grep encountered some funny characters (in a DKIM signature information line, as it happened) and decided that the file was actually binary and so it wouldn't report anything more for the rest of the file than that final line.

(This is a different and much more straightforward cause than the time GNU Grep thought some text files were binary because of a filesystem bug combined with its clever tricks.)

I generally like the GNU versions of standard Unix utilities and the things that they've added, but this is not one of them, especially when GNU Grep's output is not going to a terminal. Especially if it starts out initially printing out text lines, it should continue to do so rather than surprise people this way.

The valuable learning experience here is that any time I'm processing a text file with GNU Grep (which is pretty much all of the time in my scripts), I should explicitly force it to always treat things as text. This is unfortunately going to make some scripts more awkward, because sometimes I have pipelines with several greps involved as text is filtered and manipulated. Either I spray '-a' over all of the greps or I try to figure out what minimal LC_<something> environment variable will turn this off, or I reach for the gigantic hammer of 'LC_ALL=C' (as suggested by the GNU Grep manpage).

PS: This is not just a Linux issue because GNU Grep appears on more than just Linux machines, depending on what you install and what you add to your path. A FreeBSD machine I have access to uses GNU Grep as /usr/bin/grep, for example.

OpenBSD's 'spinning' CPU time category

Unix systems have long had a basic breakdown of what your CPU (or CPUs) was spending its time doing. The traditional division is user time, system time, idle time, and 'nice' time (which is user time for tasks that have their scheduling priority lowered through nice(1) or the equivalent), and then often 'interrupt' time, for how much time the system spent in interrupt handling. Some Unixes have added 'iowait', which is traditionally defined as 'the system was idle but one or more processes were waiting for IO to complete'. OpenBSD doesn't have iowait, but current versions have a new time category, 'spinning'.

The 'spinning' category was introduced in May of 2018, in this change:

Stopping counting and reporting CPU time spent spinning on a lock as system time.

Introduce a new CP_SPIN "scheduler state" and modify userland tools to display the % of timer a CPU spents spinning.

(This is talking about a kernel lock.)

Since this dates from early 2018, I believe it's in everything from OpenBSD 6.4 onward. It's definitely in OpenBSD 6.6. This new CPU time category is supported in OpenBSD's versions of top and systat, but it is not explicitly broken out by vmstat; in fact vmstat's 'sy' time is actually the sum of OpenBSD 'system', 'interrupt', and 'spinning'. Third party tools may or may not have been updated to add this new category.

(I don't know why OpenBSD hasn't updated vmstat. Perhaps they consider its output frozen for some reason, even though it's hiding information by merging everything together into 'sy'. The vmstat manpage is not technically lying about what 'sy' is, since all of true system time, interrupts, and spinning time are forms of time spent in the kernel, but the breakdown between those three can be important. And it means that you can't directly compare vmstat 'sy' to the system time you get from top or systat.)

Our experience is that under some loads, it's possible for a current SMP OpenBSD machine to spend quite appreciable amounts of time in this 'spinning' state. Specifically we've seen our dual CPU OpenBSD L2TP server spend roughly 33% of its time this way while people were apparently trying to push data through it as fast as they could go (which didn't actually go all that fast, perhaps because of all of that spinning).

Marking whether or not the current CPU is spinning on a kernel lock is handled in sys/kern/kern_lock.c, modifying a per-CPU scheduler state spc_spinning field. Tracking and accounting for this is handled in sys/kern/kern_clock.c, in handling the 'statistics clock' (look for use of CP_SPIN). User programs find out all of this through sysctl(2), specifically KERN_CPTIME2 and friends. All of OpenBSD's CPU time categories are found in sys/sched.h.

PS: If you're using a program that doesn't currently support the 'spinning' category, you can reverse engineer the spinning value by adding up all of the other ones and looking for what's missing. Normally, you would expect that all of the categories of CPU time add up to more or less 100%; if you have all but one of them, you can work backward to the missing one based on that. This may not be completely precise, but at least it will pick up large gaps.

Understanding X mouse cursors (and their several layers of history)

Like most if not all windowing systems, X has the concept of the mouse cursor and allows it to take on various shapes depending on what's going on and what the mouse is over. The mouse cursor is drawn by the server, which means that X programs need to have some way of telling the server what cursor shape they want at the moment (traditionally by associating a cursor shape with every window or sub-window area and then letting X work out which one to display based on where the mouse pointer was).

The X protocol (and server) come with a pre-defined set of cursors. If your program is happy with one of these, you use it by telling the X server that you want cursor number N with XCreateFontCursor(). As mentioned in the manpage (and hinted at by the function name), the server loads these cursors from a specific X font, which is exposed to clients under the special font name 'cursor'. Like the special 'fixed' font name, this isn't even a XLFD font name and so there's no way to specify what pixel size you want your cursors to be in; you get whatever (font) size the font is or the server decides on (if the X font the server is using is one where it can do that, and I'm not sure that the X server even supports resizable fonts for the special cursor font).

(The 'cursor' font is listed in 'xlsfonts' output and can be looked at with 'xfd -fn cursor'. There are often several alternate cursor fonts, which you can also look at; these would be used through XCreateGlyphCursor().)

The actual font that is the (default) cursor font can be set through a server command line argument (per XServer(1)). If not set, I believe it's whatever font called 'cursor' the X server finds while rummaging around its font directories. On my Fedora 31 machine, this font file is /usr/share/X11/fonts/misc/cursor.pcf.gz (ie, a bitmap font in PCF format, which I believe means that it has only a single size). This 'cursor' font has to be specially formatted to provide not just the actual image for each cursor but also the mask for what parts of the cursor are transparent (see here and here, and also here). This cursor font file is normally only present on machines with the X server, and because it's used (only) by the server, it only needs to be on the server's machine. In other words, this is a server side X font.

Of course, it didn't take long for people to be unhappy with the default X server cursors in the default size. In particular, people wanted themes, with their own choice of different looking cursors. Fortunately X had always provided an escape hatch for programs that wanted custom cursors; not only could they use an different font to get cursors from (although it had better be set up right), they could also define their own cursor bitmaps and masks with XCreatePixmapCursor() (and apparently there are additional options these days). So enterprising people built cursor theming on top of this, eventually with a more or less standard library for this, XCursor (see also the Arch wiki). Somewhat to my surprise, XCursor is used today even by things like xterm.

(I'm not sure how toolkits like GTK and desktops like KDE do all of this, but I think they're at least compatible with XCursor so you can use the same cursor themes and theme configuration files with both.)

Because cursor themes work by having the X client create bitmaps and then send them to the X server, they're reliant on having the cursor theme data that defines the cursors on every machine you run X programs from. This has the same drawbacks as modern X fonts do; how a given cursor theme is rendered (and if it is at all) depends on the individual client and the individual machine. If you run all of your X programs from one machine, either everything works or it doesn't. If you run your X programs from multiple machines and use a HiDPI display, you can discover that your Ubuntu machines are missing some cursor theme data files.

(Even if everyone has the same cursor theme data (and uses the same theme), they all need to agree about what size the cursors should be given various settings, your apparent display DPI, and so on.)

PS: It appears that even with XCursor, basic X programs make no attempt to scale up the size of (some) mouse cursors to match the size of other elements. For instance, I can run 'xterm -fs 24' to get pretty gigantic text, but the I-beam mouse cursor is the same size as always and so now pretty small compared to the letters themselves. Depending on your view, this may or may not be a feature; you can argue that the size of the mouse pointer you want is set by how visible various sizes are, not how well they match other elements of the window you're in. It could be pretty weird to move your mouse cursor from a big text xterm to a normal xterm and back and have the mouse cursor jump around in size.

The problem of Unix iowait and multi-CPU machines

Various Unixes have had a 'iowait' statistic for a long time now (although I can't find a source for where it originated; it's not in 4.x BSD, so it may have come through System V and sar). The traditional and standard definition of iowait is that it's the amount of time the system was idle but had at least one process waiting on disk IO. Rather than count this time as 'idle' (as you would if you had a three-way division of CPU time between user, system, and idle), some Unixes evolved to count this as a new category, 'iowait'.

(To my surprise, iowait doesn't appear to be in the *BSDs at all; they stick to the old user, system, idle, and nice divisions of system time. Iowait is in Linux and Solaris/Illumos, and appears to be in HP-UX and AIX as well based on some quick manpage checks.)

This traditional definition makes easy and straightforward sense on a uniprocessor machine, where the system cannot be simultaneously idle waiting for a process to finish IO and running a process. But these days basically all systems are multi-CPU 'SMP' ones, and in a multi-CPU world it's not obvious how you should define iowait, because there's no longer a strict binary division between 'running things' and 'stopped waiting for IO'. In a multi-CPU system, some but not all CPUs can be busy running code, while some processes are blocked on IO. If those processes had IO that completed immediately, they could run on the currently idle CPUs, but at the same time the system is doing some work instead of being entirely stalled waiting for IO to complete (which is the way iowait works on a uniprocessor system).

There are all sorts of plausible answers a Unix could adopt for the meaning of iowait on a multi-CPU system, ranging from the simple to the complex to the ad-hoc. But no matter what a Unix does, it needs to come up with some answer (and ideally document it), and there are no guarantees that two different Unixes have picked the same answer. If you're going to use iowait for much, you might want to try to figure out how your Unix defines it on multi-CPU machines.

(Picking the answer gets more complicated if your Unix wants iowait to be a per-CPU thing, like user, system, and idle time often are, because normally waiting for IO is not naturally associated with any particular CPU. Illumos appears to not consider iowait a per-CPU thing, per a little mention in the mpstat manpage; it does have the idea of iowait in general, per sar(1).)

Unix's /usr split and standards (and practice)

In Rob Landley about the /usr split, Rob Landley doesn't have very good things to say about how the split between /bin and /usr/bin (and various other directories) has continued to exist, especially in various standards. One of my views on this is that the split continuing to exist was always inevitable, regardless of why the split existed and what reasons people might have for preserving it (such as diskless workstations benefiting from it).

As far as standards go, Unix standards have pretty much always been mostly documentation standards, codifying existing practice with relatively little invention of new things. The people trying to create Unix standards are not in a position to mandate that existing Unixes change their practices and setup, and existing Unixes have demonstrated that they will just ignore attempts to do so. Writing a Unix filesystem hierarchy standard that tried to do away with /bin and mandated that /usr was on the root filesystem would have been a great way to it to fail.

(POSIX attempted to mandate some changes in the 1990s, and Unix vendors promptly exiled commands implementing those changes off to obscure subdirectories in /usr. Part of this is because being backward compatible is the path of least resistance and fewest complaints from customers.)

For actual Unixes in practice, conforming to the historical weight of existing other Unixes (including their own past releases) has always been the easiest way. There are countless people and scripts and so on that expect to find some things in /bin and some things in /usr/bin and so on, and the less you disrupt all of that the easier your life is. Inventing new filesystem layouts and pushing for them takes work; any Unix has a finite amount of work it can do and must carefully budget where that work goes. Reforming the filesystem layout is rarely a good use of limited time and work, partly because the returns on it are so low (and people will argue with you, which is its own time sink).

(Totally reinventing Unix from the ground up has been tried, by the people arguably in the best position possible to do it, and the results did not take the world by storm. Plan 9 from Bell Labs still has its fans and some of its ideas have leaked out to mainstream Unix, but that's about it.)

The modern irony about the whole issue is that recent versions of Linux distributions are increasingly requiring /usr to be on the root filesystem and merging /bin, /lib, and so on into the /usr versions, but this has been accomplished by the 800 pound gorilla of systemd, which many people are not happy about in general. The monkey's paw hopes you're happy with sort of achieving the end of this split.

(A clean end to the split would be to remove one or the other of /bin and /usr/bin, and similarly for the other duplicated directories.)

The /bin versus /usr split and diskless workstations

I was recently reading Rob Landley about the /usr split (via, which can be summarized as being not very enthused about the split between /bin and /usr/bin, and how long it lasted. I have some opinions on this as a whole, but today I want to note that one factor in keeping this split going is diskless workstations and the issue of /etc.

Unix traditionally puts a number of machine specific pieces of information in /etc, especially the machine's hostname and its IP address and basic network configuration. A straightforward implementation of a diskless Unix machine needs to preserve this, meaning that you need a machine-specific /etc and that it has to be available very early (because it will be used to bootstrap a lot of the rest of the system). The simplest way to provide a machine specific /etc is to have a machine specific root filesystem, and for obvious reasons you want this to be as small as possible. This means not including /usr (and later /var) in this diskless root filesystem, which means that you need a place in the root filesystem to put enough programs to boot the system and NFS mount the rest of your filesystems. That place might as well be /bin (and later /sbin).

This isn't the only way to do diskless Unix machines, but it's the one that involves the least changes from a normal Unix setup. All you need is some way to get the root filesystem (NFS) mounted, which can be quite hacky since it's a very special case, and then everything else is normal. An /etc that isn't machine specific and where the machine specific information is set up and communicated in some other way requires significantly more divergence from standard Unix, all of which you will have to write and maintain. And diskless Unix machines remained reasonably popular for quite some time for various reasons.

(There is potentially quite a lot of machine specific information in /etc. Although it was common for diskless Unix machines to all be the same, you could want to run different daemons on some of them, have custom crontabs set up, only allow some people to log in to certain workstations, or all sorts of other differences. And of course all of these potential customizations were spread over random files in /etc, not centralized into some configuration store that you could just provide an instance of. In the grand Unix tradition, /etc was the configuration store.)

Finding out what directories exist with only basic shell builtins (a Unix shell trick)

Back in the old days of multi-architecture Unix environments, generally no two Unix vendors could agree on what should be in your $PATH. The core of /bin and /usr/bin was the same, but everyone had their own additional directories (Solaris had a lot of them). In addition, different local computing groups had different views on where local programs should go; /usr/local/bin, /local/bin, /opt/<something>/bin, /<group>/bin, and so on. This was a problem for me because I maintained a common set of dotfiles across all of the Unix systems I had accounts on, and I didn't want my $PATH to be a giant list of every possible directory on every system. So I needed to trim down a giant master list of possible $PATH directories to only the ones that existed on the current system, and to make it harder I wanted to use only shell builtins, in a shell where test wasn't a builtin.

Fortunately, there is one thing that has to be a builtin and has to fail if a directory doesn't exist (or isn't usable by you), namely cd. Using cd as a substitute for 'test -d' is a bit odd, but it works. My shell has real lists, so I could write this as more or less:

# potential $PATH entries in $candidates
path=`{ tpath=()
        for (pe in $candidates)
           builtin cd $pe >[1=] >[2=] && tpath=($tpath $pe)
        echo $tpath }

(This doesn't work for relative paths, but I didn't have any in my $PATH.)

Because all shells have to have cd as a builtin, this same trick could be used in pretty much any shell. Bourne style shells make you work a bit harder to put together $PATH; at a minimum you need to stick :'s between every element (cf), and maybe your equivalent of $candidates also uses :'s to separate entries and so you have to split it up on those.

(In a Bourne shell I would make $candidates just be quoted and space separated, because that's a lot simpler to deal with. This wouldn't handle a $PATH entry that had spaces in it, but you don't normally see those.)

Using cd this way is a trick, but tricks are what you're forced into in a minimal shell environment where you don't want to run external programs. In actual practice, I wound up writing a little C program to do this and relying on that on systems that I used frequently enough to compile it for them. The implementation with cd was only a fallback for systems and situations without my isdirs program.

(This is sort of a followup to a Unix shell trick, which was also about something that I had to do for cross-architecture dotfiles.)

PS: All of this comes from the days when systems were slow enough that you tried to avoid running additional external programs in your shell dotfiles, which is why I wanted to do it all with shell builtins instead of running a lot of tests or the like. And most modern shells have test as a builtin anyway.