lkml.org 
[lkml]   [1996]   [Sep]   [16]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: Perl make depend made faster


On Sun, 15 Sep 1996, Luca Lizzeri wrote:
>
> I think I will just stare at mkdep.c for a couple of days and ponder on
> the ways of the wizards, hoping that I will learn as much more of C as I
> did of Perl while writing depend.pl.

Umm.. "mkdep.c" isn't exactly a thing of beauty. What it _is_ is my way of
writing state machines, and an efficient one. I don't think you should
actually show it to impressionable people, or people with heart disease.

I have fixed up "mkdep.c" to be more portable (it worked fine on Linux
systems, but if you're cross-compiling from other systems you might have had
problems with "mmap()" and "munmap()" wanting to always have a page-aligned
argument to them).

I also made it do the memory accesses a "long" at a time, which helps a lot
on architectures that don't have fast byte accesses. That should actually
speed it up on x86 too, especially the newer ones (or the really old ones
without any cache at all).

The new version is really sick, but I had fun writing it. You should compile
it with "-S -O2 -fomit-frame-pointer" to see all the subtleties by looking at
the generated assembly code.

Ok, now it's a competition: is anobody able to shave another second off this
one? On my alpha it runs in eight seconds on the whole source tree once
things are cached (22 secs on a P166).

Subtleties you should keep in mind when looking at it:
(a) use "mmap()" to avoid a copy from kernel space
(b) map in the whole file to avoid having to worry about boundary conditions
(c) do ugly things when loading a "long" at a time, it doesn't work if the
source file has NUL-characters in it
(d) partition the functions so that gcc can allocate registers sanely
(e) not so subtle: "goto" is your friend if you're doing state machines

Linus

-----
#include <stdio.h>
#include <stdlib.h>

#include <string.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>
#include <sys/fcntl.h>
#include <sys/mman.h>

char *filename, *command, __depname[256] = "\n\t@touch ";
int needsconfig, hasconfig, hasdep;

#define depname (__depname+9)

struct path_struct {
int len;
char buffer[256-sizeof(int)];
} path_array[2] = {
{ 23, "/usr/src/linux/include/" },
{ 0, "" }
};

static void handle_include(int type, char *name, int len)
{
int plen;
struct path_struct *path = path_array+type;

if (len == 14 && !memcmp(name, "linux/config.h", len))
hasconfig = 1;

plen = path->len;
memcpy(path->buffer+plen, name, len);
len += plen;
path->buffer[len] = '\0';
if (access(path->buffer, F_OK))
return;

if (!hasdep) {
hasdep = 1;
printf("%s:", depname);
}
printf(" \\\n %s", path->buffer);
}

static void handle_config(void)
{
hasconfig = 1;
if (!hasdep)
fprintf(stderr,
"%s needs config but has not included config file\n",
filename);
}

#if defined(__alpha__) || defined(__i386__)
#define LE_MACHINE
#endif

#ifdef LE_MACHINE
#define first_byte(x) current = (unsigned char) x; x >>= 8;
#else
#define first_byte(x) current = x >> 8*(sizeof(unsigned long)-1); x <<= 8;
#endif

#define GETNEXT { \
if (!__buf) { \
__buf = *(unsigned long *) next; \
if (!__buf) \
break; \
} first_byte(__buf); next++; }
#define CASE(c,label) if (current == c) goto label
#define NOTCASE(c,label) if (current != c) goto label

static void state_machine(char *next)
{
for(;;) {
unsigned long __buf = 0;
unsigned char current;

normal:
GETNEXT
__normal:
CASE('/',slash);
CASE('"',string);
CASE('\'',char_const);
CASE('#',preproc);
goto normal;

slash:
GETNEXT
CASE('*',comment);
goto __normal;

string:
GETNEXT
CASE('"',normal);
NOTCASE('\\',string);
GETNEXT
goto string;

char_const:
GETNEXT
CASE('\'',normal);
NOTCASE('\\',char_const);
GETNEXT
goto char_const;

comment:
GETNEXT
__comment:
NOTCASE('*',comment);
GETNEXT
CASE('/',normal);
goto __comment;

preproc:
GETNEXT
CASE('\n',normal);
CASE(' ',preproc);
CASE('\t',preproc);
CASE('i',i_preproc);
GETNEXT

skippreproc:
CASE('\n',normal);
GETNEXT
goto skippreproc;

i_preproc:
GETNEXT
CASE('f',if_line);
NOTCASE('n',skippreproc);
GETNEXT
NOTCASE('c',skippreproc);
GETNEXT
NOTCASE('l',skippreproc);
GETNEXT
NOTCASE('u',skippreproc);
GETNEXT
NOTCASE('d',skippreproc);
GETNEXT
NOTCASE('e',skippreproc);

/* "# include" found */
include_line:
GETNEXT
CASE('\n',normal);
CASE('<', std_include_file);
NOTCASE('"', include_line);

/* "local" include file */
{
char *incname = next;
local_include_name:
GETNEXT
CASE('\n',normal);
NOTCASE('"', local_include_name);
handle_include(1, incname, next-incname-1);
goto skippreproc;
}

/* <std> include file */
std_include_file:
{
char *incname = next;
std_include_name:
GETNEXT
CASE('\n',normal);
NOTCASE('>', std_include_name);
handle_include(0, incname, next-incname-1);
goto skippreproc;
}

if_line:
if (hasconfig)
goto skippreproc;
if_start:
if (!memcmp("CONFIG_", next, 7)) {
handle_config();
goto skippreproc;
}
GETNEXT
CASE('\n', normal);
CASE('_', if_middle);
if (current >= 'a' && current <= 'z')
goto if_middle;
if (current < 'A' || current > 'Z')
goto if_start;
if_middle:
GETNEXT
CASE('\n', normal);
CASE('_', if_middle);
if (current >= 'a' && current <= 'z')
goto if_middle;
if (current < 'A' || current > 'Z')
goto if_start;
goto if_middle;
}
}

static void do_depend(void)
{
char *map;
int mapsize;
int pagesizem1 = getpagesize()-1;
int fd = open(filename, O_RDONLY);
struct stat st;

if (fd < 0)
return;
fstat(fd, &st);
mapsize = st.st_size + 2*sizeof(unsigned long);
mapsize = (mapsize+pagesizem1) & ~pagesizem1;
map = mmap(NULL, mapsize, PROT_READ, MAP_PRIVATE, fd, 0);
if (-1 == (long)map) {
close(fd);
return;
}
state_machine(map);
munmap(map, mapsize);
if (hasdep)
puts(command);
}

int main(int argc, char **argv)
{
int len;
char * hpath;

hpath = getenv("HPATH");
if (!hpath)
hpath = "/usr/src/linux/include";
len = strlen(hpath);
memcpy(path_array[0].buffer, hpath, len);
if (len && hpath[len-1] != '/') {
path_array[0].buffer[len] = '/';
len++;
}
path_array[0].buffer[len] = '\0';
path_array[0].len = len;

while (--argc > 0) {
int len;
char *name = *++argv;

filename = name;
len = strlen(name);
memcpy(depname, name, len+1);
command = __depname;
if (len > 2 && name[len-2] == '.') {
switch (name[len-1]) {
case 'c':
case 'S':
depname[len-1] = 'o';
command = "";
}
}
needsconfig = hasconfig = hasdep = 0;
do_depend();
}
return 0;
}


\
 
 \ /
  Last update: 2005-03-22 13:38    [W:2.170 / U:3.060 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site