Book Excerpt: Linux Programming by Example, Part 2

Concluding our tour of the V7 ls command.

In Part 1 of this article, we began a tour of the V7 Unix ls program. We looked at how it parses options and at how it maintained the flist array as a two-level stack of files to print information about. We then saw how ls found and printed out the long format information about each file. This article continues the tour through the code.

238  long                           _long nblock(long size)_
239  nblock(size)
240  long size;
241  {
242      return((size+511)>>9);
243  }

The nblock() function reports how many disk blocks the file uses. This calculation is based on the file's size as returned by stat(). The V7 block size was 512 bytes--the size of a physical disk sector.

The calculation on line 242 looks a bit scary. The >>9 is a right-shift by nine bits. This divides by 512, to give the number of blocks. (On early hardware, a right-shift was much faster than division.) So far, so good. Now, a file of even one byte still takes up a whole disk block. However, 1 / 512 comes out as zero (integer division truncates), which is incorrect. This explains the size+511. By adding 511, the code ensures that the sum produces the correct number of blocks when it is divided by 512.

This calculation is only approximate, however. Very large files also have indirect blocks. Despite the claim in the V7 _ls_(1) manpage, this calculation does not account for indirect blocks.

Furthermore, consider the case of a file with large holes (created by seeking way past the end of the file with lseek()). Holes don't occupy disk blocks; however, this is not reflected in the size value. Thus, the calculation produced by nblock(), while usually correct, could produce results that are either smaller or larger than the real case.

For these reasons, the st_blocks member was added into the struct stat at 4.2 BSD, and then picked up for System V and POSIX.

245  int m1[] = { 1, S_IREAD>>0, 'r', '-' };
246  int m2[] = { 1, S_IWRITE>>0, 'w', '-' };
247  int m3[] = { 2, S_ISUID, 's', S_IEXEC>>0, 'x', '-' };
248  int m4[] = { 1, S_IREAD>>3, 'r', '-' };
249  int m5[] = { 1, S_IWRITE>>3, 'w', '-' };
250  int m6[] = { 2, S_ISGID, 's', S_IEXEC>>3, 'x', '-' };
251  int m7[] = { 1, S_IREAD>>6, 'r', '-' };
252  int m8[] = { 1, S_IWRITE>>6, 'w', '-' };
253  int m9[] = { 2, S_ISVTX, 't', S_IEXEC>>6, 'x', '-' };
255  int *m[] = { m1, m2, m3, m4, m5, m6, m7, m8, m9};
257  pmode(aflag)                         void pmode(int aflag)
258  {
259      register int **mp;
261      flags = aflag;
262      for (mp = &m[0]; mp < &m[sizeof(m)/sizeof(m[0])];)
263          select(*mp++);
264  }
266  select(pairp)                        void select(register int
267  register int *pairp;
268  {
269      register int n;
271      n = *pairp++;
272      while (--n>=0 && (flags&*pairp++)==0)
273          pairp++;
274      putchar(*pairp);
275  }

Lines 245-275 print the file's permissions. The code is compact and rather elegant; it requires careful study.

  • Lines 245-253: The arrays m1 through m9 encode the permission bits to check for along with the corresponding characters to print. There is one array per character to print in the file mode. The first element of each array is the number of (permission, character) pairs encoded in that particular array. The final element is the character to print in the event that none of the given permission bits are found.

    Note also how the permissions are specified as I_READ<<0, I_READ>>3, I_READ<<6 and so on. The individual constants for each bit (S_IRUSR, S_IRGRP, etc.) had not been invented yet. (See Table 4.5 in my book.)

  • Line 255: The m array points to each of the m1 through m9 arrays.

  • Lines 257-264: The pmode() function first sets the global variable flags to the passed-in parameter aflag. It then loops through the m array, passing each element to the select() function. The passed-in element represents one of the m1 to m9 arrays.

  • Lines 266-275: The select() function understands the layout of each m1 through m9 array. n is the number of pairs in the array (the first element); line 271 sets it. Lines 272-273 look for permission bits, checking the global variable flags set previously on line 261.

Note the use of the ++ operator, both in the loop test and in the loop body. The effect is to skip over pairs in the array as long as the permission bit in the first element of the pair is not found in flags.

When the loop ends, either the permission bit has been found, in which case pairp points at the second element of the pair, which is the correct character to print, or it has not been found, in which case pairp points at the default character. In either case, line 274 prints the character that pairp points to.

A final point worth noting is that in C, character constants (such as x) have type int, not char. This is different in C++: there, character constants do have type char. This difference does not affect this particular code. So there's no problem putting such constants into an integer array; everything works correctly.

277  char *                    _char *makename(char *dir, char *file)_
278  makename(dir, file)
279  char *dir, *file;
280  {
281      static char dfile[100];
282      register char *dp, *fp;
283      register int i;
285      dp = dfile;
286      fp = dir;
287      while (*fp)
288          *dp++ = *fp++;
289      *dp++ = '/';
290      fp = file;
291      for (i=0; i<DIRSIZ; i++)
292          *dp++ = *fp++;
293      *dp = 0;
294      return(dfile);
295  }

Lines 277-295 define the makename() function. Its job is to concatenate a directory name and a filename, separated by a slash character, and produce a string. It does this in the static buffer dfile. Note that dfile is only 100 characters long and that no error checking is done.

The code itself is straightforward, copying characters one at a time. makename() is used by the readdir() function.

297  readdir(dir)                               _void readdir(char*dir)_
298  char *dir;
299  {
300      static struct direct dentry;
301      register int j;
302      register struct lbuf *ep;
304      if ((dirf = fopen(dir, "r")) == NULL) {
305          printf("%s unreadable\n", dir);
306          return;
307      }
308      tblocks = 0;
309      for(;;) {
310          if (fread((char *)&dentry, sizeof(dentry), 1, dirf) != 1)
311              break;
312          if (dentry.d_ino==0
313           || aflg==0 && dentry.d_name[0]=='.' &&
314              || dentry.d_name[1]=='.' && dentry.d_name[2]=='\0'))
315              continue;
316          ep = gstat(makename(dir, dentry.d_name), 0);
317          if (ep==NULL)
318              continue;
319          if (ep->lnum != -1)
320              ep->lnum = dentry.d_ino;
321          for (j=0; j<DIRSIZ; j++)
322              ep->ln.lname[j] = dentry.d_name[j];
323      }
324      fclose(dirf);
325  }

Lines 297-325 define the readdir() function, whose job is to read the contents of directories named on the command line.

Lines 304-307 open the directory for reading, returning if fopen() fails. Line 308 initializes the global variable tblocks to 0. This was used earlier (lines 153-154) to print the total number of blocks used by files in a directory.

Lines 309-323 are a loop that reads directory entries and adds them to the flist array. Lines 310-311 read one entry, exiting the loop upon end-of-file.

Lines 312-315 skip uninteresting entries. If the inode number is zero, this slot isn't used. Otherwise, if -a was not given and the filename is either . or .., skip it.

Lines 316-318 call gstat() with the full name of the file, and a second argument of false, indicating that it's not from the command line. gstat() updates the global lastp pointer and the flist array. A NULL return value indicates some sort of failure.

Lines 319-322 save the inode number and name in the struct lbuf. If ep->lnum comes back from gstat() set to -1, it means that the stat() operation on the file failed. Finally, line 324 closes the directory.

The following function, gstat() (lines 327-398), is the core function for the operation of retrieving and storing file information.

327  struct lbuf *                _struct lbuf *gstat(char *file, int argfl)_
328  gstat(file, argfl)
329  char *file;
330  {
331      extern char *malloc();
332      struct stat statb;
333      register struct lbuf *rep;
334      static int nomocore;
336      if (nomocore)            _Ran out of memory earlier_
337          return(NULL);
338      rep = (struct lbuf *)malloc(sizeof(struct lbuf));
339      if (rep==NULL) {
340          fprintf(stderr, "ls: out of memory\n");
341          nomocore = 1;
342          return(NULL);
343      }
344      if (lastp >= &flist[NFILES]) {
345          static int msg;      _Check whether too many files given_
346          lastp--;
347          if (msg==0) {
348              fprintf(stderr, "ls: too many files\n");
349              msg++;
350          }
351      }
352      *lastp++ = rep;          _Fill in information_
353      rep->lflags = 0;
354      rep->lnum = 0;
355      rep->ltype = '-';        _Default file type_

The static variable nomocore [sic] indicates that malloc() failed upon an earlier call. Since it's static, it's automatically initialized to 0 (that is, false). If it's true upon entry, gstat() just returns NULL. Otherwise, if malloc() fails, ls prints an error message, sets nomocore to true, and returns NULL (lines 334-343).

Lines 344-351 make sure that there is still room left in the flist array. If not, ls prints a message (but only once; note the use of the static variable msg), and then reuses the last slot in flist.

Line 352 makes the slot lastp points to point to the new struct lbuf (rep). This also updates lastp, which is used for sorting in main() (lines 142 and 152). Lines 353-355 set default values for the flags, inode number, and type fields in the struct lbuf.

356      if (argfl || statreq) {
357          if (stat(file, &statb)<0) {           _stat() failed_
358              printf("%s not found\n", file);
359              statb.st_ino = -1;
360              statb.st_size = 0;
361              statb.st_mode = 0;
362              if (argfl) {
363                  lastp--;
364                  return(0);
365              }
366          }
367          rep->lnum = statb.st_ino;             _stat() OK, copy info_
368          rep->lsize = statb.st_size;
369          switch(statb.st_mode&S_IFMT) {
371          case S_IFDIR:
372              rep->ltype = 'd';
373              break;
375          case S_IFBLK:
376              rep->ltype = 'b';
377              rep->lsize = statb.st_rdev;
378              break;
380          case S_IFCHR:
381              rep->ltype = 'c';
382              rep->lsize = statb.st_rdev;
383              break;
384          }
385          rep->lflags = statb.st_mode & ~S_IFMT;
386          rep->luid = statb.st_uid;
387          rep->lgid = statb.st_gid;
388          rep->lnl = statb.st_nlink;
389          if(uflg)
390              rep->lmtime = statb.st_atime;
391          else if (cflg)
392              rep->lmtime = statb.st_ctime;
393          else
394              rep->lmtime = statb.st_mtime;
395          tblocks += nblock(statb.st_size);
396      }
397      return(rep);
398  }

Lines 356-396 handle the call to stat(). If this is a command-line argument or if statreq is true because of an option, the code fills in the struct lbuf as follows:

  • Lines 357-366: Call stat() and if it fails, print an error message and set values as appropriate, then return NULL (expressed as 0).

  • Lines 367-368: Set the inode number and size fields from the struct stat if the stat() succeeded.

  • Lines 369-384: Handle the special cases of directory, block device, and character device. In all cases the code updates the ltype field. For devices, the lsize value is replaced with the ltype field. For devices, the lsize value is replaced with the st_rdev value.

  • Lines 385-388: Fill in the lflags, luid, lgid and lnl fields from the corresponding fields in the struct stat. Line 385 removes the file-type bits, leaving the 12 permissions bits (read/write/execute for user/group/other, and setuid, setgid, and save-text).

  • Lines 389-394: Based on command-line options, use one of the three time fields from the struct stat for the lmtime field in the struct lbuf.

  • Line 395: Update the global variable tblocks with the number of blocks in the file.

400  compar(pp1, pp2)                     _int compar(struct lbuf_
401  struct lbuf **pp1, **pp2;            _struct lbuf_
402  {
403      register struct lbuf *p1, *p2;
405      p1 = *pp1;
406      p2 = *pp2;
407      if (dflg==0) {
408          if (p1->lflags&ISARG && p1->ltype=='d') {
409              if (!(p2->lflags&ISARG && p2->ltype=='d'))
410                  return(1);
411          } else {
412              if (p2->lflags&ISARG && p2->ltype=='d')
413                  return(-1);
414          }
415      }
416      if (tflg) {
417          if(p2->lmtime == p1->lmtime)
418              return(0);
419          if(p2->lmtime > p1->lmtime)
420              return(rflg);
421          return(-rflg);
422      }
423      return(rflg * strcmp(p1->lflags&ISARG? p1->ln.namep:
424                  p2->lflags&ISARG? p2->ln.namep: p2->ln.lname));
425  }

The compar() function is dense: there's a lot happening in little space. The first thing to remember is the meaning of the return value: A negative value means that the first file should sort to an earlier spot in the array than the second, zero means the files are equal, and a positive value means that the second file should sort to an earlier spot than the first.

The next thing to understand is that ls prints the contents of directories after it prints information about files. Thus the result of sorting should be that all directories named on the command line follow all files named on the command line.

Finally, the rflg variable helps implement the -r option, which reverses the sorting order. It is initialized to 1 (line 30). If -r is used, rflg is set to -1 (lines 89-91).

The following pseudocode describes the logic of compar(); the line numbers in the left margin correspond to those of ls.c:

     407  if LS HAS TO READ DIRECTORIES  # dflg == 0
     410              return 1    # first comes after second
                      FALL THROUGH TO TIME TEST
     411      else
                  # p1 is not a command-line directory
     413              return -1   # first comes before second
                      FALL THROUGH TO TIME TEST

     416  if SORTING IS BASED ON TIME  # tflg is true
              # compare times:
     417      if P2'S TIME IS EQUAL TO P1'S TIME
     418          return 0
     419      if P2'S TIME > P1'S TIME
              # p2's time < p1's time

     423  Multiply rflg by the result of strcmp()
     424  on the two names and return the result

The arguments to strcmp() on lines 423-424 look messy. What's going on is that different members of the ln union in the struct lbuf must be used, depending on whether the filename is a command-line argument or was read from a directory.