Book Excerpt: Linux Programming by Example, Part 1

 in
A tour through the V7 ls command.

This article is excerpted from Chapter 7 of my book Linux Programming by Example: The Fundamentals, published by Prentice Hall (ISBN: 0-13-142964-7). Chapters 1 through 6 cover the standard APIs for argument parsing, dynamic memory management, file and directory access, retrieving file information (stat(), lstat()), working with users and groups and also date and time information and sorting.

V7 code uses so called K&R C, where functions are declared without an argument list. For such declarations, we show the corresponding ANSI C style declaration on the right between underscore marks [_Collects needed info_].

Putting It All Together: ls

The V7 ls command nicely ties together everything we've seen so far. It uses almost all of the APIs we've covered, touching on many aspects of Unix programming: memory allocation, file metadata, dates and times, user names, directory reading and sorting.

1. V7 ls Options

In comparison to modern versions of ls, the V7 ls accepted only a handful of options, and the meaning of some of them is different for V7 than for current ls. The options are as follows:

  • -a: Print all directory entries. Without this, don't print . and .. Interestingly enough, V7 ls ignores only . and .. , while V1 through V6 ignore any file whose name begins with a period. This latter behavior is the default in modern versions of ls as well.

  • -c: Use the inode change time, instead of the modification time, with -t or -l.

  • -d: For directory arguments, print information about the directory itself, not its contents.

  • -f: Force each argument to be read as a directory, and print the name found in each slot. This option disables -l, -r, -s and -t and enables -a. (This option apparently existed for filesystem debugging and repair.)

  • -g: For ls -l, use the group name instead of the user name.

  • -i: Print the inode number in the first column along with the filename or the long listing.

  • -l: Provide the familiar long format output. Note, however, that V7 ls -l printed only the user name, not the user and group names together.

  • -r: Reverse the sort order, be it alphabetic for filenames or by time.

  • -s: Print the size of the file in 512-byte blocks. The V7 ls (1) manpage states that "indirect blocks"--blocks used by the filesystem for locating the data blocks of large files--are also included in the computation, but, as we shall see, this statement was incorrect.

  • -t: Sort the output by modification time, most recent first, instead of by name.

  • -u: Use the access time instead of the modification time with -t and/or -l.

The biggest differences between V7 ls and modern ls concern the -a option and the -l option. Modern systems omit all dot files unless -a is given, and they include both user and group names in the -l long listing. On modern systems, -g is taken to mean print only the group name, and -o means print only the user name. For what it's worth, GNU ls has over 50 options!

2. V7 ls Code

The file /usr/src/cmd/ls.c in the V7 distribution contains the code. It is all of 425 lines long.


  1  /*
  2   * list file or directory
  3   */
  4
  5  #include <sys/param.h>
  6  #include <sys/stat.h>
  7  #include <sys/dir.h>
  8  #include <stdio.h>
  9
 10  #define NFILES  1024
 11  FILE    *pwdf, *dirf;
 12  char    stdbuf[BUFSIZ];
 13
 14  struct lbuf {                    _Collects needed info_
 15      union {
 16          char    lname[15];
 17          char    *namep;
 18      } ln;
 19      char    ltype;
 20      short   lnum;
 21      short   lflags;
 22      short   lnl;
 23      short   luid;
 24      short   lgid;
 25      long    lsize;
 26      long    lmtime;
 27  };
 28
 29  int aflg, dflg, lflg, sflg, tflg, uflg, iflg, fflg, gflg, cflg;
 30  int rflg    = 1;
 31  long    year;             _Global variables: auto init to 0_
 32  int flags;
 33  int lastuid = -1;
 34  char    tbuf[16];
 35  long    tblocks;
 36  int statreq;
 37  struct  lbuf    *flist[NFILES];
 38  struct  lbuf    **lastp = flist;
 39  struct  lbuf    **firstp = flist;
 40  char    *dotp   = ".";
 41
 42  char    *makename();      _char *makename(char *dir, char *file);_
 43  struct  lbuf *gstat();    _struct lbuf *gstat(char *file, int argfl);_
 44  char    *ctime();         _char *ctime(time_t *t);_
 45  long    nblock();         _long nblock(long size);_
 46
 47  #define ISARG   0100000

The program starts with file inclusions (lines 5-8) and variable declarations. The struct lbuf (lines 14-27) encapsulates the parts of the struct stat that are of interest to ls. We see later how this structure is filled.

The variables aflg, dflg, and so on (lines 29 and 30) all indicate the presence of the corresponding option. This variable naming style is typical of V7 code. The flist, lastp, and firstp variables (lines 37-39) represent the files that ls reports information about. Note that flist is a fixed-size array, allowing no more than 1024 files to be processed. We see shortly how all these variables are used.

After the variable declarations come function declarations (lines 42-45), and then the definition of ISARG, which distinguishes a file named on the command line from a file found when a directory is read.


 49  main(argc, argv)                        _int main(int argc, char **argv)_
 50  char *argv[];
 51  {
 52      int i;
 53      register struct lbuf *ep, **ep1;   _Variable and function declarations_
 54      register struct lbuf **slastp;
 55      struct lbuf **epp;
 56      struct lbuf lb;
 57      char *t;
 58      int compar();
 59
 60      setbuf(stdout, stdbuf);
 61      time(&lb.lmtime);                   _Get current time_
 62      year = lb.lmtime - 6L*30L*24L*60L*60L; /* 6 months ago */

The main() function starts by declaring variables and functions (lines 52-58), setting the buffer for standard output, retrieving the time of day (lines 60-61), and computing the seconds-since-the-Epoch value for approximately six months ago (line 62). Note that all the constants have the L suffix, indicating the use of long arithmetic.


 63      if (--argc > 0 && *argv[1] == '-') {
 64          argv++;                   _Parse options_
 65          while (*++*argv) switch (**argv) {
 66
 67          case 'a':                 _All directory entries_
 68              aflg++;
 69              continue;
 70
 71          case 's':                 _Size in blocks_
 72              sflg++;
 73              statreq++;
 74              continue;
 75
 76          case 'd':                 _Directory info, not contents_
 77              dflg++;
 78              continue;
 79
 80          case 'g':                 _Group name instead of user name_
 81              gflg++;
 82              continue;
 83
 84          case 'l':                 _Long listing_
 85              lflg++;
 86              statreq++;
 87              continue;
 88
 89          case 'r':                 _Reverse sort order_
 90              rflg = -1;
 91              continue;
 92
 93          case 't':                 _Sort by time, not name_
 94              tflg++;
 95              statreq++;
 96              continue;
 97
 98          case 'u':               _Access time, not modification time_
 99              uflg++;
100              continue;
101
102          case 'c':               _Inode change time, not modification time_
103              cflg++;
104              continue;
105
106          case 'i':               _Include inode number_
107              iflg++;
108              continue;
109
110          case 'f':               _Force reading each arg as directory_
111              fflg++;
112              continue;
113
114          default:                _Ignore unknown option letters_
115              continue;
116          }
117          argc--;
118      }

Lines 63-118 parse the command-line options. Note the manual parsing code getopt() hadn't been invented yet. The statreq variable is set to true when an option requires the use of the stat() system call.

Avoiding an unnecessary stat() call on each file is a big performance win. The stat() call was particularly expensive, because it could involve a disk seek to the inode location, a disk read to read the inode, and then a disk seek back to the location of the directory contents (in order to continue reading directory entries).

Modern systems have the inodes in groups, spread out throughout a filesystem instead of clustered together at the front. This makes a noticeable performance improvement. Nevertheless, stat() calls are still not free; you should use them as needed, but not any more than that.


119      if (fflg) {                  _-f overrides -l, -s, -t, adds -a_
120          aflg++;
121          lflg = 0;
122          sflg = 0;
123          tflg = 0;
124          statreq = 0;
125      }
126      if(lflg) {                      _Open password or group file_
127          t = "/etc/passwd";
128          if(gflg)
129              t = "/etc/group";
130          pwdf = fopen(t, "r");
131      }
132      if (argc==0) {                   _Use current dir if no args_
133          argc++;
134          argv = &dotp - 1;
135      }

Lines 119-125 handle the -f option, turning off -l, -s, -t, and statreq. Lines 126-131 handle -l, setting the file to be read for user or group information. Remember that the V7 ls shows only one or the other, not both.

If no arguments are left, lines 132-135 set up argv such that it points at a string representing the current directory. The assignment argv = &dotp - 1 is valid, although unusual. The - 1 compensates for the ++argv on line 137. This avoids special case code for argc == 1 in the main part of the program.


136      for (i=0; i < argc; i++) {        _Get info about each file_
137          if ((ep = gstat(*++argv, 1))==NULL)
138              continue;
139          ep->ln.namep = *argv;
140          ep->lflags |= ISARG;
141      }
142      qsort(firstp, lastp - firstp, sizeof *lastp, compar);
143      slastp = lastp;
144      for (epp=firstp; epp<slastp; epp++) {    _Main code, see text_
145          ep = *epp;
146          if (ep->ltype=='d' && dflg==0 || fflg) {
147              if (argc>1)
148                  printf("\n%s:\n", ep->ln.namep);
149              lastp = slastp;
150              readdir(ep->ln.namep);
151              if (fflg==0)
152                  qsort(slastp,lastp - slastp,sizeof *lastp,compar);
153              if (lflg || sflg)
154                  printf("total %D\n", tblocks);
155              for (ep1=slastp; ep1<lastp; ep1++)
156                  pentry(*ep1);
157          } else
158              pentry(ep);
159      }
160      exit(0);
161  }                                _End of main()_

Lines 136-141 loop over the arguments, gathering information about each one. The second argument to gstat() is a boolean: true if the name is a command-line argument, false otherwise. Line 140 adds the ISARG flag to the lflags field for each command-line argument.

The gstat() function adds each new struct lbuf into the global flist array (line 137). It also updates the lastp global pointer to point into this array at the current last element.

Lines 142-143 sort the array using qsort() and save the current value of lastp in slastp. Lines 144-159 loop over each element in the array, printing file or directory info as appropriate.

The code for directories deserves further explication:

  • if (ep->ltype=='d' && dflg==0 || fflg) ... Line 146. If the file type is directory and if -d was not provided or if -f was, then ls has to read the directory instead of printing information about the directory itself.

  • if (argc>1) printf("\n%s:\n", ep->ln.namep) Lines 147-148. Print the directory name and a colon if multiple files were named on the command line.

  • lastp = slastp; readdir(ep->ln.namep) Lines 149-150. Reset lastp from slastp. The flist array acts as a two-level stack of filenames. The command-line arguments are kept in firstp through slastp - 1. When readdir() reads a directory, it puts the struct lbuf structures for the directory contents onto the stack, starting at slastp and going through lastp. This is illustrated in Figure 7.1.


           firstp                      slastp             lastp
              |                          |                  |
              V                          V                  V
          +--------+--------+--------+--------+--------+--------+
          | struct | struct | struct | struct | struct | struct |  flist array
          | lbuf * | lbuf * | lbuf * | lbuf * | lbuf * | lbuf * |
          +--------+--------+--------+--------+--------+--------+

          |<--- From command line -->|<---- From readdir() ---->|

Figure 7.1: The flist Array as a Two-Level Stack

  • if (fflg==0) qsort(slastp,lastp - slastp,sizeof *lastp,compar) Lines 151-152. Sort the subdirectory entries if -f is not in effect.

  • if (lflg || sflg) printf("total %D\n", tblocks) Lines 153-154. Print the total number of blocks used by files in the directory, for -l or -s. This total is kept in the variable tblocks, which is reset for each directory. The %D format string for printf() is equivalent to %ld on modern systems; it means print a long integer. (V7 also had %ld, see line 192.)

  • for (ep1=slastp; ep1>lastp; ep1++) pentry(*ep1) Lines 155-156. Print the information about each file in the subdirectory. Note that the V7 ls descends only one level in a directory tree. It lacks the modern -R recursive option.


163  pentry(ap)                                _void pentry(struct lbuf *ap)_
164  struct lbuf *ap;
165  {
166      struct { char dminor, dmajor;};       _Unused historical artifact_
167      register t;                           _from V6 ls_
168      register struct lbuf *p;
169      register char *cp;
170
171      p = ap;
172      if (p->lnum == -1)
173          return;
174      if (iflg)
175          printf("%5u ", p->lnum);          _Inode number_
176      if (sflg)
177      printf("%4D ", nblock(p->lsize));     _Size in blocks_

The pentry() routine prints information about a file. Lines 172-173 check whether the lnum field is 1, and return if so. When p->lnum == -1 is true, the struct lbuf is not valid. Otherwise, this field is the file's inode number.

Lines 174-175 print the inode number if -i is in effect. Lines 176-177 print the total number of blocks if -s is in effect. (As we see below, this number may not be accurate.)


178      if (lflg) {                              _Long listing:_
179          putchar(p->ltype);                     _-- File type_
180          pmode(p->lflags);                      _-- Permissions_
181          printf("%2d ", p->lnl);                _-- Link count_
182          t = p->luid;
183          if(gflg)
184              t = p->lgid;
185          if (getname(t, tbuf)==0)
186              printf("%-6.6s", tbuf);            _-- User or group_
187          else
188              printf("%-6d", t);
189          if (p->ltype=='b' || p->ltype=='c')    _-- Device: major/minor_
190              printf("%3d,%3d", major((int)p->lsize), minor((int)p->lsize));
191          else
192              printf("%7ld", p->lsize);          _-- Size in bytes_
193          cp = ctime(&p->lmtime);
194          if(p->lmtime < year)                   _-- Modification time_
195              printf(" %-7.7s %-4.4s ", cp+4, cp+20); else
196              printf(" %-12.12s ", cp+4);
197      }
198      if (p->lflags&ISARG)                       _-- Filename_
199          printf("%s\n", p->ln.namep);
200      else
201          printf("%.14s\n", p->ln.lname);
202  }

Lines 178-197 handle the -l option. Lines 179-181 print the file's type, permissions, and number of links. Lines 182-184 set t to the user ID or the group ID, based on the -g option. Lines 185-188 retrieve the corresponding name and print it if available. Otherwise, the program prints the numeric value.

Lines 189-192 check whether the file is a block or character device. If it is, they print the major and minor device numbers, extracted with the major() and minor() macros. Otherwise, they print the file's size.

Lines 193-196 print the time of interest. If it's older than six months, the code prints the month, day, and year. Otherwise, it prints the month, day, and time (*note Ctime::, for the format of ctime()'s result).

Finally, lines 198-201 print the filename. For a command-line argument, we know it's a zero-terminated string, and %s can be used. For a file read from a directory, it may not be zero-terminated, and thus an explicit precision, %.14s, must be used.


204  getname(uid, buf)                      _int getname(int uid, char buf[])_
205  int uid;
206  char buf[];
207  {
208      int j, c, n, i;
209
210      if (uid==lastuid)                  _Simple caching, see text_
211          return(0);
212      if(pwdf == NULL)                   _Safety check_
213          return(-1);
214      rewind(pwdf);                      _Start at front of file_
215      lastuid = -1;
216      do {
217          i = 0;                         _Index in buf array_
218          j = 0;                         _Counts fields in line_
219          n = 0;                            _Converts numeric value_
220          while((c=fgetc(pwdf)) != '\n') {  _Read lines_
221              if (c==EOF)
222                  return(-1);
223              if (c==':') {                 _Count fields_
224                  j++;
225                  c = '0';
226              }
227              if (j==0)                     _First field is name_
228                  buf[i++] = c;
229              if (j==2)                     _Third field is numeric ID_
230                  n = n*10 + c - '0';
231          }
232      } while (n != uid);                   _Keep searching until ID found_
233      buf[i++] = '\0';
234      lastuid = uid;
235      return(0);
236  }

The getname() function converts a user or group ID number into the corresponding name. It implements a simple caching scheme; if the passed-in uid is the same as the global variable lastuid, then the function returns 0, for OK; the buffer will already contain the name (lines 210-211). lastuid is initialized to -1 (line 33), so this test fails the first time getname() is called.

pwdf is already open on either /etc/passwd or /etc/group (see lines 126-130). The code here checks that the open succeeded and returns -1 if it didn't (lines 212-213).

Surprisingly, ls does not use getpwuid() or getgrgid(). Instead, it takes advantage of the facts that the format of /etc/passwd and /etc/group is identical for the first three fields (name, password, numeric ID) and that both use a colon as separator.

Lines 216-232 implement a linear search through the file. j counts the number of colons seen so far: 0 for the name and 2 for the ID number. Thus, while scanning the line, it fills in both the name and the ID number.

Lines 233-235 terminate the name buffer, set the global lastuid to the found ID number, and return 0 for OK.

In the second half of this article, we will finish our tour through the V7 ls code file.

Arnold Robbins is a professional programmer and technical author. He is the long-time maintainer of gawk, the GNU Project's version of the Awk programming language. He is the author of numerous well-known technical books, such as Linux Programming by Example: The Fundamentals, recently published by Prentice Hall, as well as Unix In A Nutshell, Learning the vi Editor and Effective awk Programming, published by O'Reilly Media Inc. He is happily married with four wonderful children. Arnold is an amateur Talmudist and particularly enjoys studying the Jerusalem Talmud. He can be reached at arnold@skeeve.com.

______________________

White Paper
Linux Management with Red Hat Satellite: Measuring Business Impact and ROI

Linux has become a key foundation for supporting today's rapidly growing IT environments. Linux is being used to deploy business applications and databases, trading on its reputation as a low-cost operating environment. For many IT organizations, Linux is a mainstay for deploying Web servers and has evolved from handling basic file, print, and utility workloads to running mission-critical applications and databases, physically, virtually, and in the cloud. As Linux grows in importance in terms of value to the business, managing Linux environments to high standards of service quality — availability, security, and performance — becomes an essential requirement for business success.

Learn More

Sponsored by Red Hat

White Paper
Private PaaS for the Agile Enterprise

If you already use virtualized infrastructure, you are well on your way to leveraging the power of the cloud. Virtualization offers the promise of limitless resources, but how do you manage that scalability when your DevOps team doesn’t scale? In today’s hypercompetitive markets, fast results can make a difference between leading the pack vs. obsolescence. Organizations need more benefits from cloud computing than just raw resources. They need agility, flexibility, convenience, ROI, and control.

Stackato private Platform-as-a-Service technology from ActiveState extends your private cloud infrastructure by creating a private PaaS to provide on-demand availability, flexibility, control, and ultimately, faster time-to-market for your enterprise.

Learn More

Sponsored by ActiveState